最小生成树

算法思想：kruskal：将边按长度从小到大排序，每次取出一条边并运用并查集检测两点之间是否已经有通路，如果有就不选，如果没有就将该边作为最小生成树的边。Prim：从1顶点开始找距离1最近的点纳入集合并更新其他点距离该集合点的距离，每次选距离集合最短路径纳入集合，直到边数等于n-1。

主要/核心函数分析：float kruskal(int n, int m)：将边按长度从小到大排序，每次取出一条边并运用并查集检测两点之间是否已经有通路，如果有就不选，如果没有就将该边作为最小生成树的边，将边的编号纳入最小生成树路径的数组中。void prim()：将1纳入集合，每次选取距离集合最近的点纳入集合，最后再更新其他点到集合的距离（同时记录该点到集合中哪个点最短便于路径的输出）。

测试数据：

4 4

1 2 1

2 3 4

2 4 2

3 4 3

运行结果：

边:

1----2

2----4

3----4

KrusKal的最小权值:6

边：

2----1

4----2

3----4

Prim的最小权值:6

时间复杂度：Prim是O（点数的平方）；Kruskal是O（边数*log边数）

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include <fstream>
  5 using namespace std;
  6 
  7 const int N = 1002;//点数
  8 const int M = 100002;//边
  9 const int INF = 100000;
 10 int n, m;//输入点数和边数
 11 int index[N];//存储生成树的边
 12 
 13 int a[N][N];
 14 bool visit[N] = {};//节点是否已经被访问 
 15 int dist[N];//顶点与集合的距离
 16 int knot[N]={0};//顶点与集合中哪一点距离最短
 17 
 18 struct edge
 19 {
 20     int x, y;//起点和终点
 21     float cost;
 22 }Edges[M];//边 
 23 
 24 int father[N];//并查集
 25 
 26 int findfather(int x)
 27 {
 28     int a = x;
 29     int z;
 30 
 31     //到这条边最初的起点
 32     while (x != father[x])
 33         x = father[x];
 34 
 35     //路径压缩
 36     while (a != father[a])
 37     {
 38         z = a;
 39         a = father[a];
 40         father[z] = x;
 41     }
 42 
 43     return x;
 44 }
 45 
 46 //比较权值
 47 bool compare(edge a, edge b) { return a.cost < b.cost; }
 48 
 49 float kruskal(int n, int m)
 50 {
 51     float sum = 0;
 52     int edgenum = 0;//权和点数
 53     
 54     for (int i = 1; i <= n; i++)
 55         father[i] = i;
 56     //初始化并查集
 57 
 58     sort(Edges, Edges + m, compare);//从小到大排序
 59 
 60     for (int i = 0; i < m; i++)
 61     {
 62         //判断该条边起点和终点在该边未加入时是否连通
 63         int fax = findfather(Edges[i].x);
 64         int fay = findfather(Edges[i].y);
 65 
 66         //不连通则可以加入
 67         if (fax != fay)
 68         {
 69             father[fax] = fay;
 70             sum += Edges[i].cost;
 71             index[edgenum++]=i;
 72             if (edgenum == n - 1)break;//找到最小生成树
 73         }
 74     }
 75     return sum;
 76 }
 77 
 78 void prim()
 79 {
 80     fill(dist, dist + N, INF);//赋初值
 81     dist[1] = 0;//将1顶点纳入生成树
 82     
 83     float sum = 0;//总费用
 84 
 85     cout << "边：" << endl;
 86     //找最小距离
 87     for (int i = 1; i <= n; i++)
 88     {
 89         int minx = -1;//记录顶点
 90         int mini = INF;//记录距离
 91 
 92         for (int j = 1; j <= n; j++)
 93         {
 94             if (visit[j] == false && dist[j] <= mini)
 95             {
 96                 minx = j;
 97                 mini = dist[j];
 98             }
 99         }//找到与当前集合距离最近的节点 
100 
101         if (minx != -1)//找到符合条件的点
102         {
103             visit[minx] = true;//第minx号点已经访问过了
104             sum += dist[minx];//加入最小生成树,该点加入集合 
105             if (i != 1)
106                 cout << minx << "----" << knot[minx] << endl;
107         }
108 
109         //更新剩余的点到集合的最短距离
110         for (int y = 1; y <= n; y++)
111         {
112             if (visit[y] == false && a[minx][y] != INF && a[minx][y] < dist[y])
113             {
114                 dist[y] = a[minx][y];
115                 knot[y] = minx;
116             }
117         }
118     }
119     cout<<"Prim的最小权值:"<<sum;
120 }
121 
122 int main()
123 {
124     fstream fp;
125     fp.open("test.txt", ios::in);
126 
127     fp >> n >> m;//初始化输入     
128     fill(a[0], a[0] + N * N, INF);//初始化
129     for (int i = 0; i < m; i++)
130     {
131         fp >> Edges[i].x >> Edges[i].y >> Edges[i].cost; //初始化输入边    
132         a[Edges[i].x][Edges[i].y] = a[Edges[i].y][Edges[i].x] = Edges[i].cost;
133     }
134     fp.close();
135 
136     float quanzhi1=kruskal(n,m);
137     cout << "边:" << endl;
138     for (int i = 0; i < n - 1; i++)
139         cout << Edges[index[i]].x << "----" << Edges[index[i]].y << endl;
140     cout << "KrusKal的最小权值:" << quanzhi1 << endl;
141 
142     prim();
143 
144     return 0;
145 }