Acwing - 算法基础课 - 笔记（九） 秒速五厘米 2022-10-12 01:32 118阅读 0赞 ### 文章目录 ### * * 搜索与图论（三） * * 最小生成树 * * Prim算法 * Kruskal算法 * 总结 * 二分图 * * 染色法 * 匈牙利算法 * 小结 ## 搜索与图论（三） ## 这一节讲解的是最小生成树和二分图 ### 最小生成树 ### 什么是最小生成树？首先，给定一个节点数是n，边数是m的无向连通图G。 则由全部的n个节点，和n-1条边构成的无向连通图被称为G的一颗生成树，在G的所有生成树中，边的权值之和最小的生成树，被称为G的最小生成树。 有两种常用算法： * Prim算法（普利姆） * 朴素版Prim（时间复杂度O(n2)，适用于稠密图） * 堆优化版Prim（时间复杂度O(mlogn)，适用于稀疏图） * Kruskal算法（克鲁斯卡尔） 适用于稀疏图，时间复杂度O(mlogm) ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70][] 对于最小生成树问题，如果是稠密图，通常选用朴素版Prim算法，因为其思路比较简洁，代码比较短，如果是稀疏图，通常选用Kruskal算法，因为其思路比Prim简单清晰。堆优化版的Prim通常不怎么用。 #### Prim算法 #### 这里只讲朴素版Prim。其算法流程如下 （其中用集合`s`表示，当前已经在连通块中的所有的点） 1. 初始化距离, 将所有点的距离初始化为+∞ 2. n次循环 1. t <- 找到不在集合s中, 且距离最近的点 2. 用t来更新其他点到集合s的距离 3. 将t加入到集合s中 注意，一个点t到集合s的距离，指的是：若点t和集合s中的3个点有边相连。则点t到集合s的距离就是，t与3个点相连的边中，权重最小的那条边的权重。 练习图：[acwing - 858: Prim算法求最小生成树][acwing - 858_ Prim] 题解：（C++） #include<iostream> #include<cstring> using namespace std; const int N = 510, INF = 0x3f3f3f3f; int n, m; int g[N][N], d[N]; bool visited[N]; void prim() { memset(d, 0x3f, sizeof d); // 初始化距离为正无穷 int sum = 0; for(int i = 1; i <= n; i++) { // 循环n次 // 选出距离集合s最小的点 int t = 0; for(int j = 1; j <= n; j++) { if(!visited[j] && d[j] <= d[t]) t = j; // 这里用<=, 可以避免对第一次选点做特判 } if(i == 1) d[t] = 0;// 第一次加入集合的点, 其到集合的距离为0 if(d[t] == INF) { // 选中的点距离是正无穷, 无效 printf("impossible\n"); return; } // 把这个点放到集合s里 visited[t] = true; sum += d[t]; // 这次放进来的 // 更新其他点到集合s的距离, for(int j = 1; j <= n; j++) { if(!visited[j] && g[t][j] != INF && g[t][j] < d[j]) { d[j] = g[t][j]; } } } printf("%d\n", sum); } int main() { memset(g, 0x3f, sizeof g); scanf("%d%d", &n, &m); while(m--) { int x, y, w; scanf("%d%d%d", &x, &y, &w); g[x][y] = min(g[x][y], w); g[y][x] = g[x][y]; } prim(); return 0; } 题解：（Java） import java.util.Scanner; /** * @Author yogurtzzz * @Date 2021/6/28 16:43 **/ public class Main { static int INF = 0x3f3f3f3f; static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { int n = readInt(), m = readInt(); int[][] g = new int[n + 1][n + 1]; for(int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) g[i][j] = INF; while(m-- > 0) { int u = readInt(), v = readInt(), w = readInt(); g[v][u] = g[u][v] = Math.min(g[u][v], w); // 无向图, 连两条边 } int res = prim(g, n); if (res == INF) System.out.println("impossible"); else System.out.println(res); } static int prim(int[][] g, int n) { int[] d = new int[n + 1]; boolean[] st = new boolean[n + 1]; for(int i = 0; i < n + 1; i++) d[i] = INF; int sum = 0; // 最小生成树的边权之和 // 循环n次, 每次选择一个不在集合s中, 但是距离集合s最小的点 for(int i = 1; i <= n; i++) { // 遍历, 找出一个不在s中, 距离最小的点 int t = 0; for(int j = 1; j <= n; j++) { if (!st[j] && d[j] <= d[t]) t = j; } if (i == 1) d[t] = 0; // 第一次选取的点, 距离应当是0 if (d[t] == INF) return INF; // 若选出来的点到集合的距离是正无穷, 则说明不联通 sum += d[t]; // 将这条边加入到生成树 st[t] = true; // 将点t加入到集合s // 更新其他点到集合的距离, 只更新和t相连的边 for(int j = 1; j <= n; j++) { if (!st[j] && g[t][j] != INF && d[j] > g[t][j]) { d[j] = g[t][j]; } } } return sum; } static int readInt() { return scanner.nextInt(); } } #### Kruskal算法 #### 基本思路： > 1. 先将所有边，按照权重，从小到大排序 > 2. 从小到大枚举每条边(a，b，w) > > 若a，b不连通，则将这条边，加入集合中（将a点和b点连接起来） Kruskal算法初始时，相当于所有点都是独立的，没有任何边。 Kruskal不需要用邻接表或者邻接矩阵来存图，只需要存所有边就可以了 其实就是并查集的简单应用，可以参考[acwing - 837: 连通块中点的数量][acwing - 837_] 练习题：[acwing - 859: Kruskal算法求最小生成树][acwing - 859_ Kruskal] 题解：（C++） #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1e5 + 10, M = 2e5 + 10; struct Edge { int a, b, w; bool operator < (const Edge& W) { return w < W.w; } } edges[M]; int n, m; int p[N]; int find(int x) { if(x != p[x]) p[x] = find(p[x]); return p[x]; } void kruskal() { // 先对所有边从小到大排序 sort(edges, edges + m); int totalW = 0, edgeCtn = 0; // 枚举全部边 for(int i = 0; i < m; i++) { int a = edges[i].a, b = edges[i].b, w = edges[i].w; a = find(a); b = find(b); if(a != b) { // 若a和b不连通, 则加入这条边 p[a] = b; // 将a和b连通 totalW += w; edgeCtn++; } } if(edgeCtn == n - 1) printf("%d\n", totalW); else printf("impossible\n"); } int main() { scanf("%d%d", &n, &m); for(int i = 0; i < m; i++) { int a, b, w; scanf("%d%d%d", &a, &b, &w); edges[i] = { a, b, w}; } for(int i = 1; i <= n; i++) p[i] = i; kruskal(); return 0; } 题解：（Java） import java.util.Arrays; import java.util.Scanner; /** * @Author yogurtzzz * @Date 2021/6/30 16:42 **/ public class Main { static class Edge implements Comparable<Edge> { int a, b, w; public Edge(int a, int b, int w) { this.a = a; this.b = b; this.w = w; } @Override public int compareTo(Edge o) { return w - o.w; } } static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { int n = readInt(), m = readInt(); Edge[] edges = new Edge[m]; int[] p = new int[n + 1]; for(int i = 0; i < m; i++) { int a = readInt(), b = readInt(), w = readInt(); edges[i] = new Edge(a, b, w); } // 初始化所有点都是孤立的 for(int i = 1; i <= n; i++) p[i] = i; kruskal(edges, n, m, p); } static void kruskal(Edge[] edges, int n, int m, int[] p) { // 1. 先按权重从小到大, 对所有边排序 Arrays.sort(edges); int totalWeight = 0, edgeCtn = 0; // 2. 遍历所有边 for(int i = 0; i < m; i++) { int a = edges[i].a, b = edges[i].b, w = edges[i].w; a = find(a, p); b = find(b, p); if (a != b) { // a和b还不连通, 则连接 p[a] = b; totalWeight += w; edgeCtn++; } } // 若存在最小生成树, 则加入的边一共是 n-1 条 if (edgeCtn == n - 1) System.out.println(totalWeight); else System.out.println("impossible"); } static int find(int x, int[] p) { if (x != p[x]) p[x] = find(p[x], p); return p[x]; } static int readInt() { return scanner.nextInt(); } } #### 总结 #### 与最短路的算法思想类似，求解最小生成树的算法，也是分别从**点的维度**与**边的维度**出发 * Prim 思想有点类似最短路中的Dijkstra。从**点的维度**出发，使用一个集合`s`来表示当前已纳入连通块的点。用`d[i]`来表示节点`i`与集合`s`的距离。注意，一个节点`i`与一个连通块的距离，指的是，这个节点到连通块中任意点的边权的最小值。 假设连通块中已经有了3个点`a, b, c`，现在有一个点`d`，它与`a`有一条边相连，且边权为4，与`b`的边权为6，与`c`的边权为2。则`d`与这个连通块的距离就是2。 初始时，连通块`s`中没有点，为空。所有点到连通块`s`的距离初始化为`+∞`。我们先随便选一个点（比如1号点），将`d[1]`设为0，表示这个点到连通块`s`的距离为0，从这个点开始扩展，建立最小生成树。 循环n次，每次选取一个与连通块距离最小的点，将该点加入连通块`s`，并通过这个点的出边，去更新其他点到连通块的距离。 即，每次选择一个点，加入到最小生成树。每次选择哪个点呢，选择与当前连通块距离最小的点。 一个点的加入伴随着一条边的加入（除了第一个点）。 所以最终只要加入了n-1条边，就表明n个点已经全部加入了连通块，最小生成树构建完成。 实际代码中，也是通过一个布尔数组，来维护每个点是否已计入连通块。 其实某个点`i`到连通块的距离`d[i]`，一定是这个点到连通块中某个点的边，且一定是边权最小的那个边。所以这样就能保证，每次迭代加入一个点到连通块中，都是以最小的代价（最小权重的边）将这个点加入到连通块中的。所以最终就能保证得到的连通块是最小生成树。 * Kruskal 从**边的维度**出发，先将全部边按照权重从小到大排序。然后遍历全部边，每次查看这条边的左右两个端点，是否处于同一个连通块。若不是，则将这条边加入到最小生成树中，并把两个端点放入到同一连通块。这样，当遍历完全部的边之后，会尽可能地将所有点加入到同一个连通块中。且每次是仅当两个点不在连通块时，才将这条边加入，而边是从小到大排序的。这样就能保证尽可能以小的代价，来构造生成树。所以最终得到的就是最小生成树。 注意kruskal的算法流程中，为了确定2个点是否处于同一连通块，需要用到并查集。 ### 二分图 ### 首先，什么是二分图呢？ 二分图指的是，可以将一个图中的所有点，分成左右两部分，使得图中的所有边，都是从左边集合中的点，连到右边集合中的点。而左右两个集合内部都没有边。图示如下 ![20210701095048363.png][] 这一节讲了2部分内容，分别是**染色法**和**匈牙利算法**。 其中**染色法**是通过深度优先遍历实现，时间复杂度是O(n×m)；**匈牙利算法**的时间复杂度理论上是O(n×m)，但实际运行时间一般远小于O(n×m)。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70 1][] 图论中的一个重要性质：**一个图是二分图，当且仅当图中不含奇数环** 奇数环，指的是这个环中边的个数是奇数。（环中边的个数和点的个数是相同的） 在一个环中，假设共有4个点（偶数个），由于二分图需要同一个集合中的点不能互相连接。 则1号点属于集合A，1号点相连的2号点就应当属于集合B，2号点相连的3号点应当属于集合A，3号点相连的4号点应当属于集合B。4号点相连的1号点应当属于集合A。这样是能够二分的。 而若环中点数为奇数，初始时预设1号点属于集合A，绕着环推了一圈后，会发现1号点应当属于集合B。这就矛盾了。所以存在奇数环的话，这个图一定无法二分。 可以用染色法来判断一个图是否是二分图，使用深度优先遍历，从根节点开始把图中的每个节点都染色，每个节点要么是黑色要么是白色（2种），只要染色过程中没有出现矛盾，说明该图是一个二分图，否则，说明不是二分图。 #### 染色法 #### 练习题：[acwing - 860: 染色法判定二分图][acwing - 860_] 先上个错误解法 #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1e5 + 10, M = 2e5 + 10; // 使用邻接表来存储图 int h[N], e[M], ne[M], idx; int n, m; int color[N]; void add(int x, int y) { // 链表的头插法 e[idx] = y; ne[idx] = h[x]; h[x] = idx++; } bool dfs(int x) { // 深搜这个节点的全部子节点 for(int i = h[x]; i != -1; i = ne[i]) { int u = e[i]; // 子节点 if(color[u] == -1) { // 子节点还未染色, 则直接染色, 并深搜 color[u] = !color[x]; if(!dfs(u)) return false; } else if(color[u] == color[x]) return false; // 若子节点和父节点颜色一致, 则说明矛盾 } // 深搜结束, 未出现矛盾, 则染色成功, 判定是二分图 return true; } int main() { memset(h, -1, sizeof h); // 初始化空链表 memset(color, -1, sizeof color); // 颜色初始化为-1, 表示还未染色 scanf("%d%d", &n, &m); while(m--) { int x, y; scanf("%d%d", &x, &y); add(x, y); // 无向图, 加两条边 add(y, x); } color[1] = 0; // 给1号点先染个色 // 不能直接从一个点进行dfs，因为可能整个图不是一个连通图 // 而其他的连通块不一定是二分图 // 所以要对1~n所有点依次进行染色 if(dfs(1)) printf("Yes\n"); else printf("No\n"); return 0; } 不能直接从一个点直接进行dfs，因为可能整个图不是一个连通图，此时若从一个点进行dfs，则只能把这个点所在的连通块都染色，无法触及到其他的连通块，而其他的连通块不一定是个二分图，所以要对1~n所有点依次进行染色，确保全部点都被染色。 正确解法如下 #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1e5 + 10, M = 2e5 + 10; // 由于是无向图, 需要建两条边, 所以边数设为2倍 // 使用邻接表来存储图 int h[N], e[M], ne[M], idx; // 注意这里单链表的实现, 数组大小开为M int n, m; int color[N]; void add(int x, int y) { // 链表的头插法 e[idx] = y; ne[idx] = h[x]; h[x] = idx++; } bool dfs(int x) { // 深搜这个节点的全部子节点 for(int i = h[x]; i != -1; i = ne[i]) { int u = e[i]; // 子节点 if(color[u] == -1) { // 子节点还未染色, 则直接染色, 并深搜 color[u] = !color[x]; if(!dfs(u)) return false; } else if(color[u] == color[x]) return false; // 若子节点和父节点颜色一致, 则说明矛盾, 自环应该也算矛盾? } // 深搜结束, 未出现矛盾, 则染色成功, 判定是二分图 return true; } int main() { memset(h, -1, sizeof h); // 初始化空链表 memset(color, -1, sizeof color); // 颜色初始化为-1, 表示还未染色 scanf("%d%d", &n, &m); while(m--) { int x, y; scanf("%d%d", &x, &y); add(x, y); add(y, x); } bool flag = true; // 依次对所有点进行染色 for(int i = 1; i <= n; i++) { if(color[i] == -1) { // 该点还未染色, 则直接染色, 随便染一个色即可(0或1), 并dfs, dfs完成后, 就对这个点所在的连通块都染上了色 color[i] = 0; // 进行dfs, 若在对这个连通块染色的过程中出现矛盾, 则直接break if(!dfs(i)) { flag = false; break; } } } if(flag) printf("Yes\n"); else printf("No\n"); return 0; } 题解：Java import java.util.*; /** * @Author yogurtzzz * @Date 2021/6/30 16:42 **/ public class Main { static Scanner scanner = new Scanner(System.in); static int[] h, e, ne; static int idx; static int[] color; public static void main(String[] args) { int n = readInt(), m = readInt(); h = new int[n + 1]; e = new int[2 * m + 1]; ne = new int[2 * m + 1]; color = new int[n + 1]; Arrays.fill(h, -1); while(m-- > 0) { int a = readInt(), b = readInt(); add(a, b); add(b, a); } boolean flag = true; // 染色 for(int i = 1; i <= n; i++) { if (color[i] == 0) { // 还没有被染色 color[i] = 1; // 染色 if (!dfs(i)) { // 深搜, 深搜结束后该点所在的连通块的所有点都会被染色 flag = false; break; } } } if (flag) System.out.println("Yes"); else System.out.println("No"); } static boolean dfs(int x) { for(int i = h[x]; i != -1; i = ne[i]) { int u = e[i]; if (color[u] == 0) { // 还未被染色, 直接染 color[u] = 3 - color[x]; // 染完深搜 if (!dfs(u)) return false; } else if (color[u] == color[x]) return false; } return true; } static void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } static String readString() { return scanner.next(); } static int readInt() { return scanner.nextInt(); } } 课后题：[acwing - 257: 关押罪犯][acwing - 257_] 可以使用二分图来做，也可以使用并查集 //TODO #### 匈牙利算法 #### 匈牙利算法，是给定一个二分图，用来求二分图的最大匹配的。 给定一个二分图G，在G的一个子图M中，M的边集中的任意两天边，都不依附于同一顶点，则称M是一个**匹配**。就是每个点只会有一条边相连，没有哪一个点，同时连了多条边。（参考yxc的例子：男生女生恋爱配对，最多能凑出多少对） 所有匹配中包含边数最多的一组匹配，被称为二分图的最大匹配。其边数即为最大匹配数 假设一个二分图，左半边部分节点表示男生，右半边部分节点表示女生。一个男生节点和一个女生节点连了一条边，则表示这两个人之间有感情基础，可以发展为情侣。当我们把一对男女凑成一对时，称为这两个节点匹配。 匈牙利算法的核心思想是：我们枚举左半边所有男生（节点），每次尝试给当前男生找对象。我们先找到这个男生看上的全部女生。（即找到这个节点连接的所有右侧的节点）。遍历这些女生，当一个女生没有和其他男生配对时，直接将这个女生和这个男生配对。则该男生配对成功。当这个女生已经和其他男生配对了，则尝试给这个女生的男朋友，找一个备胎。如果这个女生的男朋友有其他可选择的备胎。则将这个女生的男朋友和其备胎配对。然后将这个女生和当前男生配对。如此找下去… 练习题：[acwing - 861: 二分图的最大匹配][acwing - 861_] #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1010, M = 1e5 + 10; int h[N], e[M], ne[M], idx; int match[N]; bool st[N]; // 状态变量 int n1, n2, m; void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } // 给一个男生找女朋友 bool find(int x) { // 找出这个男生所有看上的女生 for(int i = h[x]; i != -1; i = ne[i]) { int u = e[i]; // 女生节点编号 if(st[u]) continue; // 如果这个女生已经被标记, 则跳过 st[u] = true; // 先把这个女生标记, 使得后续递归时时跳过这个女生 if(match[u] == 0 || find(match[u])) { // 如果当前这个女生没有被匹配, 或者能够给这个女生已匹配的男生另外找个备胎, 则可以 match[u] = x; return true; } } return false; // 找了一圈还是不行 } int main() { memset(h, -1, sizeof h); scanf("%d%d%d", &n1, &n2, &m); while(m--) { int a, b; scanf("%d%d", &a, &b); add(a, b); // 只从左半边连到右半边 } // 枚举左半边所有点 int res = 0; for(int i = 1; i <= n1; i++) { // 每次给一个男生找女朋友时, 清空状态变量 memset(st, false, sizeof st); if(find(i)) res++; } printf("%d\n", res); return 0; } 课后题：[acwing - 372: 棋牌摆放][acwing - 372_] //TODO #### 小结 #### 二分图相关的算法主要有2个 * 染色法：是用来判断一个图是否是二分图的 * 匈牙利算法：是用来求二分图的最大匹配的 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70]: /images/20221005/bbba870e03fe4dfc8acd3543ea0a7d70.png [acwing - 858_ Prim]: https://www.acwing.com/problem/content/860/ [acwing - 837_]: https://www.acwing.com/problem/content/839 [acwing - 859_ Kruskal]: https://www.acwing.com/problem/content/861/ [20210701095048363.png]: /images/20221005/047faeee326e46c6b2f8398e2b6758f3.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70 1]: /images/20221005/756c6d886c3d4f029de3c72c1f3b0b40.png [acwing - 860_]: https://www.acwing.com/problem/content/862/ [acwing - 257_]: https://www.acwing.com/problem/content/259/ [acwing - 861_]: https://www.acwing.com/problem/content/863/ [acwing - 372_]: https://www.acwing.com/problem/content/374/
相关 Acwing - 算法基础课 - 笔记（五） 文章目录 数据结构（二） Trie树 练习题：\[Acwing - 835: Trie字符串统计\](http 约定不等于承诺〃/ 2022年10月06日 04:59/ 0 赞/ 151 阅读
冷不防
àì夳堔傛蜴生んèń
今天药忘吃喽~
还没有评论，来说两句吧...