Loading... ## Prim算法 prim 算法干的事情是：给定一个无向图，在图中选择若干条边把图的所有节点连起来。要求边长之和最小。在图论中，叫做求最小生成树。 prim 算法采用的是一种贪心的策略。每次将离连通部分的最近的点和点对应的边加入的连通部分，连通部分逐渐扩大，最后将整个图连通起来，并且边长之和最小。 我们将图中各个节点用数字 1 ~ n 编号。  要将所有景点连通起来，并且边长之和最小，步骤如下： 1. 用一个 state 数组表示节点是否已经连通。state[i] 为真，表示已经连通，state[i] 为假，表示还没有连通。初始时，state 各个元素为假。即所有点还没有连通。用一个 dist 数组保存各个点到连通部分的最短距离，dist[i] 表示 i 节点到连通部分的最短距离。初始时，dist 数组的各个元素为无穷大。用一个 pre 数组保存节点的是和谁连通的。pre[i] = k 表示节点 i 和节点 k 之间需要有一条边。初始时，pre 的各个元素置为 -1。  2. 从 1 号节点开始扩充连通的部分，所以 1 号节点与连通部分的最短距离为 0，即disti[1] 置为 0。  3. 遍历 dist 数组，找到一个还没有连通起来，但是距离连通部分最近的点，假设该节点的编号是 i。i节点就是下一个应该加入连通部分的节点，stata[i] 置为 1。用青色点表示还没有连通起来的点，红色点表示连通起来的点。这里青色点中距离最小的是 dist[1]，因此 state[1] 置为 1。  4. 遍历所有与 i 相连但没有加入到连通部分的点 j，如果 j 距离连通部分的距离大于 i j 之间的距离，即 dist[j] > w[i][j]（w[i][j] 为 i j 节点之间的距离），则更新 dist[j] 为 w[i][j]。这时候表示，j 到连通部分的最短方式是和 i 相连，因此，更新pre[j] = i。与节点 1 相连的有 2， 3， 4 号节点。1->2 的距离为 100，小于 dist[2]，dist[2] 更新为 100，pre[2] 更新为1。1->4 的距离为 140，小于 dist[4]，dist[4] 更新为 140，pre[2] 更新为1。1->3 的距离为 150，小于 dist[3]，dist[3] 更新为 150，pre[3] 更新为1。重复 3 4步骤，直到所有节点的状态都被置为 1.  5. 此时 dist 数组中保存了各个节点需要修的路长，加起来就是。pre 数组中保存了需要选择的边。  ```java import java.util.Arrays; import java.util.Scanner; public class Main { static int N = 510, INF = 0x3f3f3f3f; static int n, m; static int [][] g = new int[N][N]; static int [] dist = new int[N]; static boolean[] st = new boolean[N]; private static int prime() { Arrays.fill(dist, INF); int res = 0; for (int i = 0; i < n; i ++) { int t = -1; for (int j = 1; j <= n; j ++) { if (!st[j] && (t == -1 || dist[t] > dist[j])) { t = j; } } if (i != 0 && dist[t] == INF) return INF; if (i != 0) { res += dist[t]; } for (int j = 1; j <= n; j ++) { dist[j] = Math.min(dist[j], g[t][j]); } st[t] = true; } return res; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); for (int i = 0; i < N; i++) { Arrays.fill(g[i], INF); } while (m -- > 0) { int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt(); g[a][b] = g[b][a] = Math.min(g[a][b], c); } int t = prime(); if (t == INF) System.out.println("impossible"); else System.out.println(t); } } ``` ## kruskal算法 算法思路： 将所有边按照权值的大小进行升序排序，然后从小到大一一判断。 如果这个边与之前选择的所有边不会组成回路，就选择这条边分；反之，舍去。 直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。 筛选出来的边和所有的顶点构成此连通网的最小生成树。 判断是否会产生回路的方法为：使用并查集。 在初始状态下给各个个顶点在不同的集合中。、 遍历过程的每条边，判断这两个顶点的是否在一个集合中。 如果边上的这两个顶点在一个集合中，说明两个顶点已经连通，这条边不要。如果不在一个集合中，则要这条边。 ```java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; //一、创建能够按照权值从小到大存储边的集合 class Edge implements Comparable<Edge>{ int s,t,w; Edge(int s,int t,int w){ this.s = s; this.t = t; this.w = w; } @Override //实现Comparable接口，重写compareTo方法，便于Arrays.sort()方法排序 public int compareTo(Edge e) { // TODO 自动生成的方法存根 return Integer.compare(w, e.w);//this.w > e.w时，返回1 } } class Main{ //零、声明基本变量 static int N = 100010; static int M = 200010; static int INF = 0x3f3f3f3f; static int n,m; static Edge[] edge = new Edge[M];//边集合 static int[] p = new int[N];//并查集 //二、编写并查集相关方法 //2.1 并查集核心：find方法 public static int find(int x){ if(p[x] != x) p[x] = find(p[x]); return p[x]; } //2.2 合并：在Kruskal中体现 //三、编写Kruskal方法 public static int kruskal(){ //3.0 声明变量 int res = 0;//同prim，记录当前最小生成树边的权重之和 int cnt = 0;//记录当前最小生成树边的数量 //3.1 将边按权值排序 //重要，对边按权值进行排序;Arrays.sort(int[] a, int fromIndex, int toIndex) Arrays.sort(edge,0,m); //3.2 从小到大枚举所有边 for(int i = 0;i < m;i ++){//(1)共m条边，故循环m次 //(2)获取当前边的起/终点与权值 int s = edge[i].s; int t = edge[i].t; int w = edge[i].w; //(3)利用并查集，判断这两个点是否在同一[集合/连通块/最小生成树]中 s = find(s); t = find(t); if(s != t){ //(4)如果不在同一集合，就将ab这条边加入该集合 p[s] = t;//利用并查集将边加入集合，即p[find(s)] = find(t) res += w;//更新当前最小生成树总长 cnt ++;//计算边数 } } //3.3 树中有n个节点便有n-1条边,如果cnt不等于n-1的话,说明无法生成有n个节点的树 if(cnt < n - 1) return INF; //3.4 返回权值之和 return res; } //四、主方法中执行指令 public static void main(String[] args) throws IOException { //4.1 输入输出 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] s1 = br.readLine().split(" "); n = Integer.parseInt(s1[0]); m = Integer.parseInt(s1[1]); //4.2 初始化并查集，读入边 for(int i = 1;i <= n;i ++) p[i] = i; for(int i = 0;i < m;i ++){ String[] s2 = br.readLine().split(" "); int a = Integer.parseInt(s2[0]); int b = Integer.parseInt(s2[1]); int w = Integer.parseInt(s2[2]); edge[i] = new Edge(a,b,w); } //4.3 调用方法，得到结果 int t = kruskal(); if(t == INF) System.out.println("impossible"); else System.out.println(t); } } ``` ## 二分图 ### 判断二分图-染色法 有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中，每个顶点集中没有边直接相连接！ 说人话的定义：图中点通过移动能分成左右两部分，左侧的点只和右侧的点相连，右侧的点只和左侧的点相连。下图就是个二分图：  如果判断一个图是不是二分图？ - 开始对任意一未染色的顶点染色。 - 判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色。 - 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断。 - bfs和dfs可以搞定！ ```java /** * 染色法 * 将所有点分成两个集合，使得所有边只出现在集合之间，就是二分图 * 二分图：一定不含有奇数环， 不一定是连通图 * dfs版本 * 代码思路： * 染色可以使用1和2区分不同颜色，用0表示未染色 * 遍历所有点，每次将未染色的点进行dfs, 默认染成1或者2 * 由于某个点染色成功不代表整个图就是二分图,因此只有某个点染色失败才能立刻break/return * 染色失败相当于至少存在2个点染了相同的颜色 */ import java.io.*; import java.util.*; class Main{ static BufferedReader read = new BufferedReader(new InputStreamReader(System.in)); static int N = 200010, n, m, idx; static int[] e = new int[N], ne = new int[N], adj = new int[N]; static int[] vi = new int[N]; public static boolean dfs(int curNode, int color){ vi[curNode] = color; for(int i = adj[curNode]; i != -1; i = ne[i]){ int nextNode = e[i]; if(vi[nextNode] == 0) { if(!dfs(nextNode, 3 - color)) return false; }else if(vi[nextNode] == color) return false; } return true; } public static void main(String[] args)throws Exception{ String[] s = read.readLine().split(" "); n = Integer.valueOf(s[0]); m = Integer.valueOf(s[1]); Arrays.fill(adj, -1); while(m-- >0){ s = read.readLine().split(" "); int a = Integer.valueOf(s[0]); int b = Integer.valueOf(s[1]); add(a, b); add(b, a); } boolean flag = true; for(int i = 1; i <= n; i++){ if(vi[i] == 0){ boolean rs = dfs(i, 1); if(!rs) { flag = false; break; } } } if(flag) System.out.println("Yes"); else System.out.println("No"); } public static void add(int a, int b){ e[idx] = b; ne[idx] = adj[a]; adj[a] = idx++; } } ``` ### 匈牙利算法-求最大匹配数量 锲而不舍算法🐶 ```java /* yls奇妙比喻，左半部比作男孩，右半部比作女孩 时间复杂度：最坏O(nm)，但是一般情况下，效果非常好 */ import java.util.*; public class Main { static int N = 510, M = 100010; static int n1, n2, m; static int h[] = new int[N], e[] = new int[M], ne[] = new int[M], idx = 0; // match[i]:不为0，就标志i被右半部的一个点匹配了，存的值是：与i相匹配的左边点 static int[] match = new int[N]; // 这个是在find(match[j])的时候起作用，表达的意思是，我让出这个女孩，看是否还有其他的女孩可以和我匹配 // st[i]：为true表示，在某一轮的匹配中右半部的i号点已经被匹配了。在某一轮（主函数中的一次for循环）起作用 static boolean[] st = new boolean[N]; static void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx ++; } static boolean find(int x) { // 遍历当前点指向右半部的点。(就是找当前男生是否能够找到一个女朋友) for(int i = h[x]; i != -1; i = ne[i]) { int j = e[i]; // 如果这一次轮次女生还没有找到男朋友，就可以参加匹配 if(!st[j]) { st[j] = true; /* 如果当前这个右半部的点j没有被匹配，则左半部的点x可以匹配这个点 * 或者当前match[j]可以匹配其它右边的点（也就是原来左半部与j相匹配的点， * 可以去匹配其它右半部的点）, * 则左半部的点x也可以匹配这个点，返回匹配成功 * */ if(match[j] == 0 || find(match[j])) { // 匹配成功 match[j] = x; return true; } } } // 表示当前点找不到一个右半部的点与之相匹配 // 表示当前男生找不到一个女朋友 return false; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); n1 = sc.nextInt(); n2 = sc.nextInt(); m = sc.nextInt(); // 邻接表的必要初始化 Arrays.fill(h, -1); while(m -- > 0) { int a = sc.nextInt(), b = sc.nextInt(); // 虽然是无向图，由于只要记左半部往右半部的连线，所以只需要添加一边即可 add(a, b); } int res = 0; for(int i = 1; i <= n1; i ++) { // 只要一次for循环起作用，所以下一次for循环的时候必须重新赋初值 Arrays.fill(st, false); // 如果当前i这个点匹配成功，就让计数加一 if(find(i)) res ++; } System.out.println(res); } } ``` 最后修改：2023 年 04 月 01 日 © 允许规范转载 赞 1 如果觉得我的文章对你有用，请随意赞赏