图论-最小生成树模板

ans 表示最小生成树中的边权和

Prim

概述：从点集（初始时为任意一个点）可以到达的点（不在该点集中）中，选离该点集距离最短的一个，加入该点集，更新 ans 。重复上面的操作直到没有点可以到达（优先队列为空）。如果这时点集中点的数量不等于原图点的数量说明原图不是连通图，无解。

 1     int Beg = 1, cnt = 0;//把 1 号点作为树的根节点；cnt 记录当前树中节点数 
 2     for (i = 1; i <= N; ++i) dis[i] = INF;
 3     dis[Beg] = 0, Q.push(Edge(Beg, 0));
 4     while (!Q.empty() && cnt != N) {
 5         Edge p = Q.top(); Q.pop();
 6         if (mk[p.v]) continue;//注意这里，类似 Dijkstra 中对于无效的优先队列中的成员的处理方式：跳过该次循环
 7         mk[p.v] = true, ++cnt, ans += p.w;
 8         for (i = 0; i != G[p.v].size(); ++i)
 9             if (!mk[G[p.v][i].v] && dis[G[p.v][i].v] > G[p.v][i].w)
10                 dis[G[p.v][i].v] = G[p.v][i].w, Q.push(G[p.v][i]);
11     }

Kruskal

概述：将所有边按权值从小到大排序，依次讨论。将两端在不同的并查集中的边，加入最小生成树中并更新 ans ，然后把它的两端所在并查集合并（初始时每个点各自在不同并查集中）。

 1     int cnt = 0;
 2     while (!Q.empty())
 3     {
 4         Edge p = Q.top();
 5         Q.pop();
 6         int t1 = Getdad(p.u), t2 = Getdad(p.v);
 7         if (t1 != t2) {
 8             ans += p.w, Dad[t1] = t2;
 9             if (++cnt == N-1) break;//N 个节点的树有 N-1 条边 
10         }
11     }

测试题目 NKOJ2747