最小生成树我喜欢用克鲁斯塔尔（kruskal）算法（主要是方便） kruskal算法求最小生成树的主要思想是贪心，其中也用到了并查集，时间复杂度也很低为O(E * lgE),可以解决诸如全村通路畅通工程问题，如hduoj1233 由于我对图的了解相对薄弱，所以只能拉来神犇的博客https://blog.csdn.net/luoshixian099/article/details/51908175/（如有冒犯还请谅解或联系我本人即刻删除） 关于图的几个概念定义： 连通图：在无向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该无向图为连通图。 强连通图：在有向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该有向图为强连通图。 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。  下面介绍两种求最小生成树算法 1.Kruskal算法 此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。 1. 把图中的所有边按代价从小到大排序； 2. 把图中的n个顶点看成独立的n棵树组成的森林； 3. 按权值从小到大选择边，所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。 4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。 ​​​​ --------------------- 本文来自 勿在浮砂筑高台 的CSDN 博客 ，全文地址请点击：https://blog.csdn.net/luoshixian099/article/details/51908175?utm_source=copy 现在讲讲我的浅显认识： 要想学会kruskal算法，首先我们要学习并查集的知识，这个我就不说了，这里给出一般并查集的查找（find）和合并（join）两个函数代码 const int maxn = 1010; int f[maxn]; int find(int x) { if (x != f[x]) f[x] = find(f[x]); return f[x]; } void join(int x,int y) { int fx = find(x),fy = find(y); if (fx != fy) f[fx] = fy; } 那么kruskal算法的实现就很简单了，我们只需把每条边的权值从小到大排序，对于两个集合我们选取集合中连接两个点的最小权值，它们的和即是我们要求的结果，来看一道例题： hduoj1233： 还是畅通工程 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 60442    Accepted Submission(s): 27450 Problem Description 某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。 Input 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N为0时，输入结束，该用例不被处理。 Output 对每个测试用例，在1行里输出最小的公路总长度。 Sample Input 3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0 Sample Output 3 5 思路： 上面我们已经说了最小生成树的做法了，那么只需要照做就好了 代码： #include<cstdio> #include<algorithm> using namespace std; const int maxn = 110; int f[maxn]; int find(int x) { if (x != f[x]) f[x] = find(f[x]); return f[x]; } void join(int x,int y) { int fx = find(x),fy = find(y); if (fx != fy) f[fx] = fy; } struct node { int u,v,cost; }road[5050]; bool cmp(node a,node b) { return a.cost < b.cost; } int main() { int n; while (~scanf("%d",&n) && n) { int m = n * (n - 1) / 2; for (int i = 1;i <= n;i ++) f[i] = i; int ans = 0,cnt = 1; for (int i = 0;i < m;i ++) scanf("%d %d %d",&road[i].u,&road[i].v,&road[i].cost); sort(road,road + m,cmp); for (int i = 0;i < m;i ++) { if (cnt == n)//小优化 break; if (find(road[i].u) != find(road[i].v)) { cnt ++; ans += road[i].cost; join(road[i].u,road[i].v); } } printf("%d\n",ans); } return 0; 当然，最小生成树还有一个算法是prim算法，这里就不说了（主要是不会）