最小生成树

2024-03-11 21:01:19

---恢复内容开始---

最小生成树的算法分为 prim和kruscal算法

初始状态：

设置2个数据结构：

lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MST

mst[i]:表示对应lowcost[i]的起点，即说明边<mst[i],i>是MST的一条边，当mst[i]=0表示起点i加入MST

我们假设V1是起始点，进行初始化（*代表无限大，即无通路）：

lowcost[2]=6，lowcost[3]=1，lowcost[4]=5，lowcost[5]=*，lowcost[6]=*

mst[2]=1，mst[3]=1，mst[4]=1，mst[5]=1，mst[6]=1，（所有点默认起点是V1）

明显看出，以V3为终点的边的权值最小=1，所以边<mst[3],3>=1加入MST

此时，因为点V3的加入，需要更新lowcost数组和mst数组：

lowcost[2]=5，lowcost[3]=0，lowcost[4]=5，lowcost[5]=6，lowcost[6]=4

mst[2]=3，mst[3]=0，mst[4]=1，mst[5]=3，mst[6]=3

明显看出，以V6为终点的边的权值最小=4，所以边<mst[6],6>=4加入MST

此时，因为点V6的加入，需要更新lowcost数组和mst数组：

lowcost[2]=5，lowcost[3]=0，lowcost[4]=2，lowcost[5]=6，lowcost[6]=0

mst[2]=3，mst[3]=0，mst[4]=6，mst[5]=3，mst[6]=0

明显看出，以V4为终点的边的权值最小=2，所以边<mst[4],4>=4加入MST

此时，因为点V4的加入，需要更新lowcost数组和mst数组：

lowcost[2]=5，lowcost[3]=0，lowcost[4]=0，lowcost[5]=6，lowcost[6]=0

mst[2]=3，mst[3]=0，mst[4]=0，mst[5]=3，mst[6]=0

明显看出，以V2为终点的边的权值最小=5，所以边<mst[2],2>=5加入MST

此时，因为点V2的加入，需要更新lowcost数组和mst数组：

lowcost[2]=0，lowcost[3]=0，lowcost[4]=0，lowcost[5]=3，lowcost[6]=0

mst[2]=0，mst[3]=0，mst[4]=0，mst[5]=2，mst[6]=0

很明显，以V5为终点的边的权值最小=3，所以边<mst[5],5>=3加入MST

lowcost[2]=0，lowcost[3]=0，lowcost[4]=0，lowcost[5]=0，lowcost[6]=0

mst[2]=0，mst[3]=0，mst[4]=0，mst[5]=0，mst[6]=0

至此，MST构建成功，如图所示：

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 #define MAX 100
 6 #define MAXCOST 0xfffffff
 7 
 8 int graph[MAX][MAX];
 9 int lowcost[MAX];
10 int mst[MAX];
11 int n,sum = 0;
12 
13 int prim()
14 {
15     int min,minid;
16     for (int i=2;i<=n;i++)
17     {
18         lowcost[i] = graph[1][i];
19         mst[i] = 1;
20     }
21     mst[1] = 0;
22     for (int i=2;i<=n;i++)
23     {
24         min = MAXCOST;
25         minid = 0;
26         for (int j=2;j<=n;j++)
27         {
28             if (lowcost[j] < min && lowcost[j]!=0)
29             {
30                 min = lowcost[j];
31                 minid = j;
32             }
33         }
34         sum += min;
35         lowcost[minid] = 0;
36         for (int j=2;j<=n;j++)
37         {
38             if (graph[minid][j] < lowcost[j])
39             {
40                 lowcost[j] = graph[minid][j];
41                 mst[j] = minid;
42             }
43         }
44     }
45     return sum;
46 }
47 
48 int main()
49 {
50     int m;
51     cin >> n >> m;    // n代表图的顶点，m代表图的边
52     //初始化图
53     for (int i=1;i<=n;i++)
54     {
55         for (int j=1;j<=n;j++)
56         {
57             graph[i][j] = MAXCOST;
58         }
59     }
60     //构造图
61     for (int k=1;k<=m;k++)
62     {
63         int i,j,cost;
64         cin >> i >> j >> cost;
65         graph[i][j] = graph[j][i] = cost;
66     }
67     cout << prim() << endl;
68     return 0;
69 }

View Code

kruscal算法是使用了并查集。始终选择当前可用的最小边权的边（可以直接快排或者algorithm的sort）。每次选择边权最小的边链接两个端点是kruskal的规则，并实时判断两个点之间有没有间接联通。

同样的，模拟过程