Minimum Spanning Tree

说到最小生成树(Minimum Spanning Tree),首先要对以下的图论概念有所了解。

图(Graph)是表示物件与物件之间的关系的数学对象,是图论的基本研究对象。图的定义方式有两种,其一是二元组定义。图G是一个有序二元组(V,E),其中V称为顶集(Vertices Set),E称为边集(Edges set),E与V不相交。它们亦可写成V(G)和E(G)。

边的方向

边是有方向的,单方向(如只允许从点a到达点b)的边称为单向边有向边;允许双方互达的边称为双向边无向边。包含单向边的图称为单向图,不包含单向边的称为无向图

带权图

图上的边或者点都可以带有权值,带权值的图就称为带权图。

子图

任取图G的若干点,以及这些点在G中存在的若干边构成的集合称为G的子图。

连通图

如果无向图G的任意点都可以直接或间接地到达其余所有点,那么G就称为连通图。

树是一种特殊的图,树上的所有点与其他点之间有且仅有一条直接或间接路径。性质:|V|=|E|+1。

生成树

如果连通图G的一个子图是一棵包含G的所有顶点的树,则该子图称为G的生成树。显然对于同一个图,生成树并不唯一。

最小生成树 定义

图G的最小生成树(假设存在)是边权和最小的生成树。

算法

Prim和Kruskal

Prim

Prim又称加点法。

步骤

•在G中任意选取一个结点v_1,置V={v_1},E=∅,k=1

•在V-V中选取与某个v_i ∈V邻接的结点v_j ,使得边(v_i , v_j)权值最小,置V=V∪{v_j },E=E∪{(v_i ,v_j )},k=k+1

•重复第二步,直到k=|V|

复杂度

$$
O(\mid V\mid^2)
$$

模板 // cost 0~n-1 // 不连通 return -1 const int INF = 0x3f3f3f3f; const int MAXN = 110; bool vis[MAXN]; int lowc[MAXN]; int Prim(int cost[][MAXN], int n) { int ans = 0; memset(vis, false, sizeof(vis)); vis[0] = true; for (int i = 1; i < n; i++) lowc[i] = cost[0][1]; for (int i = 1; i < n; i++) { int minc = INF; int p = -1; for (int j = 0; j < n; j++) { if (!vis[j] && minc > lowc[j]) { minc = lowc[j]; p = j; } } if (minc == INF) { return -1; } ans += minc; vis[p] = true; for (int j = 0; j < n; j++) { if (!vis[j] && lowc[j] > cost [p][j]) { lowc[j] = cost[p][j]; } } } return ans; } Kruskal

Kruskal又称加边法。

步骤

•在G中选取最小权边e_1,置i=1

•当i=n-1时,结束,否则进行下一步

•设已选取的边为e_1 ,e_2,……, e_i ,在G中选取不同于以上的边e_i+1,使得{e_1 ,e_2,……, e_i , e_i+1}中无回路且e_i+1是满足此条件的最小权边。

•置i=i+1,转第二步

复杂度

$$
O(\mid E\mid \log \mid E \mid)
$$

模板 const int MAXM = 10000; // 边 const int MAXN = 110; // 点 int F[MAXN]; // 并查集 struct Edge { int u, v, w; // 起点、终点、权值 }edge[MAXN]; int tol; // 边数,加边算法,初始为零 void AddEdge(int u, int v, int w) { edge[tol].u = u; edge[tol].v = v; edge[tol++].w = w; } bool CMP(Edge a, Edge b) { return a.w < b.w; } int Find(int x) { return x == F[x] ? x : F[x] = Find(x); } // n 为图的点总数 int Kruskal(int n) { memset(F, -1, sizeof(F)); sort(edge, edge + tol, CMP); int cnt = 0, ans = 0; for (int i = 0; i < tol; i++) { int u = edge[i].u; int v = edge[i].v; int w = edge[i].w; int t1 = Find(u); int t2 = Find(v); if (t1 != t2) { ans += w; F[t1] = t2; cnt++; } if (cnt == n - 1) { break; } } return cnt < n - 1 ? -1 : ans; }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zypfws.html