第8章 更多精彩算法
第1节 镖局运镖–图的最小生成树（Kruskal）
从某一起点可以到达任意点，路径的总长度最短。
算法基本思想：首先选择最短的一条边，然后选择次短的边，…一直选择n-1条边。但是新加入的边不能构成回路，也就是说，如果边的两端顶点连通了，就不能再加入了。而判断两个点是否连通，可以使用并查集（7.4）。
//测试数据 6 9 2 4 11 3 5 13 4 6 3 5 6 4 2 3 6 4 5 7 1 2 1 3 4 9 1 3 2 //结果 19
package ch8; import java.util.Scanner; public class Test1 { class edge{ int u; int v; int w; } edge[] e = new edge[10]; int n,m;//n个顶点，m条边 int[] f= new int[7];//f大小是n+1 int sum = 0; int count = 0; { for(int i=0;i<e.length;i++) { e[i] = new edge(); } } //快速排序 void quicksort(int left,int right) { if(left>right) { return; } int i = left; int j = right; while(i!=j) { while(e[j].w>=e[left].w && i<j) { j--; } while(e[i].w<=e[left].w && i<j) { i++; } if(i<j) { edge t = e[i]; e[i] = e[j]; e[j] = t; } } edge t = e[left]; e[left] = e[i]; e[i] = t; quicksort(left,i-1); quicksort(i+1,right); return; } //寻找祖先 int getf(int v) { if(f[v]==v) { return v; }else { f[v] = getf(f[v]); return f[v]; } } int merge(int v,int u) { int t1 = getf(v); int t2 = getf(u); if(t1!=t2) { //不在同一集合时合并，返回1 f[t2] = t1; return 1; } return 0; } //main public static void main(String[] args) { Scanner sc = new Scanner(System.in); Test1 t1 = new Test1(); t1.n = sc.nextInt(); t1.m = sc.nextInt(); for(int i=1;i<=t1.m;i++) { t1.e[i].u = sc.nextInt(); t1.e[i].v = sc.nextInt(); t1.e[i].w = sc.nextInt(); } //快速排序 t1.quicksort(1, t1.m); //并查集初始化 for(int i=1;i<=t1.n;i++) { t1.f[i] = i; } //Kruskal算法核心 for(int i=1;i<=t1.m;i++) { if(t1.merge(t1.e[i].u, t1.e[i].v) == 1) { t1.count++; t1.sum += t1.e[i].w; } if(t1.count == t1.n-1) { break; } } System.out.println(t1.sum); } }
第2节 再谈最小生成树（Prim）
先随便选择一个点，然后选择一条最短的边，这样就有2个点连接在一起了。接着在从2个点的边里寻找最短的边，并且要能连接到没有连接的其他点。这样每次加入一个点。
package ch8; import java.util.Scanner; public class Test2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); final int inf = 999999; int count = 0; int sum = 0; int n = sc.nextInt(); int m = sc.nextInt(); int book[] = new int[n+1]; //标记点是否在树中 int[] dis = new int[n+1]; //树到点的距离 int[][] e = new int[n+1][n+1];//存储图 //初始化e for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) { e[i][j] = 0; }else { e[i][j] = inf; } } } //读入m条边 for(int i=1;i<=m;i++) { int t1 = sc.nextInt(); int t2 = sc.nextInt(); int t3 = sc.nextInt(); e[t1][t2] = t3; e[t2][t1] = t3; } //初始化dis for(int i=1;i<=n;i++) { dis[i]=e[1][i]; } //Prim核心部分 book[1] = 1; count++; while(count<n) { int min = inf; int j=0; for(int i=1;i<=n;i++) { if(book[i]==0 && dis[i]<min) { min = dis[i]; j = i; } } book[j]=1; count++; sum +=dis[j]; //更新树到顶点的距离 for(int k=1;k<=n;k++) { if(book[k]==0&& dis[k]>e[j][k]) { dis[k] = e[j][k]; } } } System.out.println(sum); } }
使用堆存储图的话，可以降低时间复杂度。
第3节 重要城市–图的割点
割点：能将图分成不同部分的点，去掉割点后图不再连通。
求割点的方法：从某个点开始进行深度优先遍历，遍历每个点，遍历到顶点u时，如果有未访问的顶点v在不经过u的情况下不能回到已经访问的点，则说明u是割点。
测试数据 6 7 1 4 1 3 4 2 3 2 2 5 2 6 5 6 结果 2
package ch8; import java.util.Scanner; public class Test3 { int n,m;//n个顶点，m条边 int [][] e = new int[9][9];//使用e存储图，实际应该使用邻接表存储。 int root; int [] num = new int[9]; //顶点时间戳 int [] low = new int[9]; //顶点能够访问到的最早时间戳 int [] flag = new int[9];//标记是否是割点 int index; //用来进行时间戳的递增 //求两个数中较小的数 int min(int a,int b) { return a<b ? a : b; } //深度优先遍历 void dfs(int cur, int father) { int child = 0; //在生成树中cur顶点的儿子数 index++; //时间戳递增 num[cur] =index; low[cur] =index; //枚举与cur相连的所有顶点i for(int i=1;i<=n;i++) { if(e[cur][i]==1) { //i和cur相连 if(num[i]==0) { //如果num[i]==0，说明i没被访问过 child++; //cur的儿子+1 dfs(i,cur); //继续深度优先遍历 //更新cur的最早时间戳 low[cur] = min(low[cur],low[i]); //如果cur不是根节点且满足low[i]>=num[cur]，则cur是割点 if(cur!=root && low[i]>=num[cur]) { flag[cur]=1; } //如果cur是根节点且 有两个儿子，则这个根节点是割点 if(cur==root && child==2) { flag[cur]=1; } }else if(i!=father) { //i曾经被访问过，且i不是cur的父亲，则需要更新low[cur] low[cur] = min(low[cur],num[i]); } } } } //初始化图，读入边 public void init(Scanner sc) { n = sc.nextInt(); m = sc.nextInt(); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { e[i][j] = 0; } } for(int i=1;i<=m;i++) { int x = sc.nextInt(); int y = sc.nextInt(); e[x][y] = 1; e[y][x] = 1; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); Test3 t = new Test3(); t.init(sc); t.root = 1; t.dfs(1,t.root); //从1号顶点开始深度优先遍历 for(int i=1;i<=t.n;i++) { if(t.flag[i] ==1) { System.out.print(" "+i); } } } }
第4节 关键道路–图的割边
只要将low[v]>=num[u] 改为ow[v]>num[u] 。相等时表示可以回到父亲，去掉等号表示连父亲都回不到了（也回不到祖先）。如果既不能回到父亲，也不能回到祖先，那么u-v这条边就是割边。
测试数据 6 6 1 4 1 3 4 2 3 2 2 5 5 6 结果 5 - 6 2 - 5
package ch8; import java.util.Scanner; public class Test3 { int n,m;//n个顶点，m条边 int [][] e = new int[9][9];//使用e存储图，实际应该使用邻接表存储。 int root; int [] num = new int[9]; //顶点时间戳 int [] low = new int[9]; //顶点能够访问到的最早时间戳 int [] flag = new int[9];//标记是否是割点 int index; //用来进行时间戳的递增 //求两个数中较小的数 int min(int a,int b) { return a<b ? a : b; } //深度优先遍历 void dfs(int cur, int father) { int child = 0; //在生成树中cur顶点的儿子数 index++; //时间戳递增 num[cur] =index; low[cur] =index; //枚举与cur相连的所有顶点i for(int i=1;i<=n;i++) { if(e[cur][i]==1) { //i和cur相连 if(num[i]==0) { //如果num[i]==0，说明i没被访问过 child++; //cur的儿子+1 dfs(i,cur); //继续深度优先遍历 //更新cur的最早时间戳 low[cur] = min(low[cur],low[i]); //满足low[i]>num[cur]，则cur-i是割边 if(low[i]>num[cur]) { System.out.println(cur+" - "+i); flag[cur]=1; } }else if(i!=father) { //否则，i曾经被访问过，且i不是cur的父亲，则需要更新low[cur] low[cur] = min(low[cur],num[i]); } } } } //初始化图，读入边 public void init(Scanner sc) { n = sc.nextInt(); m = sc.nextInt(); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { e[i][j] = 0; } } for(int i=1;i<=m;i++) { int x = sc.nextInt(); int y = sc.nextInt(); e[x][y] = 1; e[y][x] = 1; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); Test3 t = new Test3(); t.init(sc); t.root = 1; t.dfs(1,t.root); //从1号顶点开始深度优先遍历 } }
第5节 我要做月老–二分图最大匹配
测试数据 6 5 1 4 1 5 2 5 2 6 3 4 结果 3
package ch8; import java.util.Scanner; public class Test5 { int [][]e; int [] match; int [] book; int n,m; int sum; int dfs(int u) { for(int i=1;i<=n;i++) { if(book[i]==0 && e[u][i] ==1) { //i没有访问过且 可以和u配对 book[i] = 1; if(match[i]==0 || dfs(match[i])==1) { //i没有配对过，或match[i]找到了新的配对 match[i] = u; match[u] = i; return 1; } } } return 0; } void init() { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); e = new int[n+1][n+1]; for(int i=1;i<=m;i++) { int t1 = sc.nextInt(); int t2 = sc.nextInt(); e[t1][t2] = 1; e[t2][t1] = 1; } match = new int[n+1]; book = new int[n+1]; } public static void main(String[] args) { Test5 t = new Test5(); t.init(); for(int i=1;i<=t.n;i++) { for(int j=1;j<=t.n;j++) { t.book[j] = 0; } if(t.dfs(i)==1) { //寻找增广路 t.sum++; } } System.out.println(t.sum); } }
