文件名称：最 小生成树.zip
文件大小：198KB
文件格式：ZIP
更新时间：2022-06-30 04:03:16
最小生成树
Kruskal（克鲁斯卡尔算法）算法介绍： 设G=（V，E）是无向带权连通图，V={1，2，…，n}；设最小生成树T=（V，TE），该树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），Kruskal算法将这n个顶点看成是n个孤立的连通分支。它首先将所有的边按权值从小到大排序，然后只要T中选中的边数不到n−1，就做如下的贪心选择：在边集E中选取权值最小的边E（i，j），如果将边E（i，j）加入集合TE中不产生回路（圈），则将边E（i，j）加入边集TE中，即用边E（i，j）将这两个连通分支合并连接成一个连通分支；否则继续选择下一条最短边。把边E（i，j）从集合E中删去。继续上面的贪心选择，直到T中所有顶点都在同一个连通分支上为止。此时，选取到的n−1条边恰好构成G的一棵最小生成树T。这里还存在一个问题就是判断加入某条边后图T会不会出现回路，这时候要用到避圈法，所谓避圈法就是如果所选择加入的边的起点和终点都在T的集合中，那么就可以断定一定会形成回路（圈），既边的两个结点不能属于同一集合。（这里可以用到并查集合并联通块）
【文件预览】：
最小生成树算法实现及其复杂度分析.docx
prime.cpp
kruskal.cpp