Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说
无向图最小割_图的最小度的概念,希望能够帮助你!!!。

用Stoer-Wagner算法求无向图最小割。

定理：对于图中任意两点 s 和 t 来说，无向图 G 的最小割要么为 s 到 t 的割，要么是生成图 G / {s, t} 的割（意思是把 s 和 t 合并）。

那么算法的主步骤就是求出当前图中某两点的最小割，并将这两点合并。

快速求当前图某两点的最小割的方式：
（1）维护一个集合A，初始里面只有v₁这个点（可以任意）；
（2）取一个最大的w(A, y)的点 y 放进 A 集合（集合到点的权值为集合内所有点到该点的权值和）；
（3）反复2步骤，直到 A 集和 G 集相等；
（4）设最后两个添加的点为 s 和 t，那么w(G - {t}, t)的值就是 s 到 t 的 cut 值。

struct Stoer_Wagner //可以利用优先队列将复杂度优化到O(nm + n^2^logn)  { 
    int n, g[maxn][maxn], b[maxn], dist[maxn]; //g[i][j] 表示 i 和 j 两点之间的最大流量 void init(int nn, int w[maxn][maxn]) { 
    int i, j; n = nn; for(i = 1; i <= n; ++i) for(j = 1; j <= n; ++j) g[i][j] = w[i][j]; } int Min_Cut_Phase(int ph, int & x, int & y) { 
    int i, j, t; b[t = 1] = ph; for(i = 1; i <= n; ++i) if(b[i] != ph) dist[i] = g[1][i]; for(i = 1; i < n; ++i) { 
    x = t; for(t = 0, j = 1; j <= n; ++j) if(b[j] != ph && (!t || dist[j] > dist[t])) t = j; b[t] = ph; for(j = 1; j <= n; ++j) if(b[j] != ph) dist[j] += g[t][j]; } return y = t, dist[t]; } void Merge(int x, int y) { 
    int i; if(x > y) swap(x, y); for(i = 1; i <= n; ++i) if(i != x && i != y) g[i][x] += g[i][y], g[x][i] += g[i][y]; if(y == n) return; for(i = 1; i < n; ++i) if(i != y) { 
    swap(g[i][y], g[i][n]); swap(g[y][i], g[n][i]); } } int Min_Cut() { 
    int i, ret = 0x3fffffff, x, y; memset(b, 0, sizeof(b)); for(i = 1; n > 1; ++i, --n) { 
    ret = min(ret, Min_Cut_Phase(i, x, y)); Merge(x, y); } return ret; } } 

今天的分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。