图-最小生成树

最小生成树 Minimum Spanning Tree MST

最小生成树

假设要在n个城市之间建立通讯网,则连通n个城市只需要修剪n-1条线路,如何在最节省经费的前提下建立这个通讯网?答案是:最小生成树。

Prim算法

基本思想
从一个点出发找出到邻接点权值最小的顶点,然后从这两个顶点中找出邻接点权值最小的顶点,
然后从这三个顶点找出邻接点权值最小的顶点,依次类推。

图解

算法实现

  • lowcost[i]:表示以i为终点的最小权值
  • mst[i]: 表示lowcost[i]的起点




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int prim(int graph[][MAX], int n)  
{
int lowcost[MAX];
int mst[MAX];
int i, j, min, minid, sum = 0;
for (i = 2; i <= n; i++) {
lowcost[i] = graph[1][i];
mst[i] = 1;
}
mst[1] = 0;
for (i = 2; i <= n; i++) {
min = MAXCOST;
minid = 0;
for (j = 2; j <= n; j++) {
if (lowcost[j] < min && lowcost[j] != 0) {
min = lowcost[j];
minid = j;
}
}
cout << "V" << mst[minid] << "-V" << minid << "=" << min << endl;
sum += min;
lowcost[minid] = 0;
for (j = 2; j <= n; j++) {
if (graph[minid][j] < lowcost[j]) {
lowcost[j] = graph[minid][j];
mst[j] = minid;
}
}
}
return sum;
}

kruskal算法

基本思想
找出权值最小的、再找出权值次小的、依次类推。如果其中已经有连线,则换下一个。

图解

xpisme wechat
微信号