挺久之前就学会了kruskal了，但是因为这个算法看起来非常的麻烦，没理解 ，所以一直到最近数据结构学习才认真的研究了一下，懂了之后其实挺简单的。不过要记住的是，只有无向网图才有生成树。 首先先文字讲一下过程吧，然后在配合图片进行讲解。 我们已知一个图的顶点集合为 U, 和一个已选取点的集合V。然后随机选取一个顶点，从U中删除，并加入到V中以它作为树根进行操作。 接下来就是一个循环操作，每次都找到集合中所有点和不在集合中的点的最小边，sum加上它的权重，并把这个点加入到V中，并从U中删除。直到所有的点都在V中循环结束。 来一波图解，文字可能许多人不懂。 对于上面的图来说，U集合为{1, 2, 3, 4, 5}。我们随机选取一个点，比如说选取1，并把它加入到V集合，所以U={2, 3, 4, 5}, V = {1}。 然后找到和1相连的点最小的权重值为2，因此把顶点2加进来。现在的sum=2。 上图红色圈内的点为V集合内的点，接下来在看V集合中所有的点和不在V集合中的点最小的权重是多少，很轻松找到了3，然后把4加到V集合，并从U集合减去4。sum = 5 循环上面的过程，找到了权重为1的边，和它相连的是顶点3，所以把顶点3加进来，并从U中删除。sum =6 最后找到权重为4的边，并且把5加进来。sum = 10 到此为止我们就找到了最小生成树，并且它的权重为10。
到现在为止思想我们就讲完了，在说一点实现的问题。 1），V集合其实就是一个标记数组vis，标记了就代表加入到V集合了，并且从U中删除了。 2），就是每次如何去找这个权重最小的边呢？这里它并不是暴力取遍历整个V集合，而是从一开始就有一个dis数组，它里面存的是当前V集合中的所有最小的权重，并且每次新加入一个顶点就判断它能不能更新dis数组。比如上图一开始我们选择顶点1，所以dis = {INF, 2, INF, 3, 6}（INF代表无穷远）。当选择顶点2后，dis = {INF, 2, 9, 3, 6}。实际就是把所有V中的顶点进行缩点，看作一个大点。因此一开始不能到达的顶点3也可以到达了。
#include <iostream> #include <vector> #include <cstring> using namespace std; const int MAX_N = 50001; const int INF = 0x3f3f3f3f; int dis[MAX_N], vis[MAX_N]; struct edge { int to, cost; edge(int t, int c):to(t), cost(c) {} }; vector<edge> G[MAX_N]; void add_edge(int from, int to, int cost) { G[from].push_back(edge(to, cost)); G[to].push_back(edge(from, cost)); } int prim(int v, int n) { memset(dis, INF, sizeof(dis)); vis[v] = true; int sum = 0; //把自己选取的第一个点周围的边赋值给dis数组 for (int i=0; i<G[v].size(); i++) { dis[G[v][i].to] = G[v][i].cost; } //只需要循环n-1次就可以了，因为自己设置的顶点已经处理过了 for (int i=1; i<n; i++) { int index = 0, minnum = INF; //找到当前dis数组内最小边 for (int j=1; j<=n; j++) { if (!vis[j] && dis[j] < minnum) { minnum = dis[j]; index = j; } } vis[index] = true; sum+=minnum; //检查新加进来的点和其他没加进来的点的权重能不能更新dis数组 for (int j=0; j<G[index].size(); j++) { if (!vis[G[index][j].to] && dis[G[index][j].to] > G[index][j].cost) { dis[G[index][j].to] = G[index][j].cost; } } } return sum; } int main() { int n, m; cin >> n >> m; for (int i=0; i<m; i++) { int x, y, cost; cin >> x >> y >> cost; add_edge(x, y, cost); } //随便选取一个点进行操作 cout << prim(1, n) << endl; return 0; }