最小生成树概念(转载)
假设一个国家有一些城市,这些城市可以互相连接起来,假设每两个城市之间的道路有很多条,那么一定存在这样的情况,可以用最少的路程连接各个城市。
以上这个问题就可以归纳为最小生成树问题,用正式的表述方法描述为:给定一个无方向的带权图G=(V, E)
,最小生成树为集合T
, T
是以最小代价连接V
中所有顶点所用边E
的最小集合。 集合T
中的边能够形成一颗树,这是因为每个节点(除了根节点)都能向上找到它的一个父节点。
而Prim
算法和Kruskal
算法,就分别从点和边下手解决了该问题。
Prim算法
Prim
算法是一种产生最小生成树的算法。该算法于1930
年由捷克数学家沃伊捷赫·亚尔尼克(英语:Vojtěch Jarník
)发现;并在1957
年由美国计算机科学家罗伯特·普里姆(英语:Robert C. Prim
)独立发现;1959
年,艾兹格·迪科斯彻再次发现了该算法。
Prim
算法从任意一个顶点开始,每次选择一个与当前顶点集最近的一个顶点,并将两顶点之间的边加入到树中。Prim
算法在找当前最近顶点时使用到了贪婪算法。
算法描述:
1. 在一个加权连通图中,顶点集合V
,边集合为E
2. 任意选出一个点作为初始顶点,标记为visit
,计算所有与之相连接的点的距离,选择距离最短的,标记visit
.
3. 重复以下操作,直到所有点都被标记为visit
:
在剩下的点钟,计算与已标记visit
点距离最小的点,标记visit
,证明加入了最小生成树。
下面我们来看一个最小生成树生成的过程:
1 起初,从顶点a
开始生成最小生成树
2 选择顶点a
后,顶点啊置成visit
(涂黑),计算周围与它连接的点的距离:
3 与之相连的点距离分别为7
,6
,4
,选择C
点距离最短,涂黑C
,同时将这条边高亮加入最小生成树:
4 计算与a,c
相连的点的距离(已经涂黑的点不计算),因为与a
相连的已经计算过了,只需要计算与c
相连的点,如果一个点与a,c
都相连,那么它与a
的距离之前已经计算过了,如果它与c的距离更近,则更新距离值,这里计算的是未涂黑的点距离涂黑的点的最近距离,很明显,b
和a
为7
,b
和c
的距离为6
,更新b
和已访问的点集距离为6
,而f
,e
和c
的距离分别是8
,9
,所以还是涂黑b
,高亮边bc
:
5 接下来很明显,d
距离b
最短,将d
涂黑,bd
高亮:
6 f
距离d
为7
,距离b
为4
,更新它的最短距离值是4
,所以涂黑f
,高亮bf
:
7 最后只有e
了:
针对如上的图,代码实例如下:
1 #include<bits/stdc++.h> 2 #define INF 10000 3 using namespace std; 4 const int N = 6; 5 bool visit[N]; 6 int dist[N] = { 0, }; 7 int graph[N][N] = { {INF,7,4,INF,INF,INF}, //INF代表两点之间不可达 8 {7,INF,6,2,INF,4}, 9 {4,6,INF,INF,9,8}, 10 {INF,2,INF,INF,INF,7}, 11 {INF,INF,9,INF,INF,1}, 12 {INF,4,8,7,1,INF} 13 }; 14 int prim(int cur) 15 { 16 int index = cur; 17 int sum = 0; 18 int i = 0; 19 int j = 0; 20 cout << index << " "; 21 memset(visit,false, sizeof(visit)); 22 visit[cur] = true; 23 for(i = 0; i < N; i++) 24 dist[i] = graph[cur][i];//初始化,每个与a邻接的点的距离存入dist 25 for(i = 1; i < N; i++) 26 { 27 int minor = INF; 28 for(j = 0; j < N; j++) 29 { 30 if(!visit[j] && dist[j] < minor) //找到未访问的点中,距离当前最小生成树距离最小的点 31 { 32 minor = dist[j]; 33 index = j; 34 } 35 } 36 visit[index] = true; 37 cout << index << " "; 38 sum += minor; 39 for(j = 0; j < N; j++) 40 { 41 if(!visit[j] && dist[j]>graph[index][j]) //执行更新,如果点距离当前点的距离更近,就更新dist 42 { 43 dist[j] = graph[index][j]; 44 } 45 } 46 } 47 cout << endl; 48 return sum; //返回最小生成树的总路径值 49 } 50 int main() 51 { 52 cout << prim(0) << endl;//从顶点a开始 53 return 0; 54 }
Kruskal算法
Kruskal是另一个计算最小生成树的算法,其算法原理如下。首先,将每个顶点放入其自身的数据集合中。然后,按照权值的升序来选择边。当选择每条边时,判断定义边的顶点是否在不同的数据集中。如果是,将此边插入最小生成树的集合中,同时,将集合中包含每个顶点的联合体取出,如果不是,就移动到下一条边。重复这个过程直到所有的边都探查过。
下面还是用一组图示来表现算法的过程:
1 初始情况,一个联通图,定义针对边的数据结构,包括起点,终点,边长度:
typedef struct _node{ int val; //长度 int start; //边的起点 int end; //边的终点 }Node;
2 在算法中首先取出所有的边,将边按照长短排序,然后首先取出最短的边,将a
,e
放入同一个集合里,在实现中我们使用到了并查集的概念:
3 继续找到第二短的边,将c
, d
再放入同一个集合里:
4 继续找,找到第三短的边ab
,因为a
,e
已经在一个集合里,再将b
加入:
5 继续找,找到b
,e
,因为b
,e
已经同属于一个集合,连起来的话就形成环了,所以边be
不加入最小生成树:
6 再找,找到bc
,因为c
,d
是一个集合的,a
,b
,e
是一个集合,所以再合并这两个集合:
这样所有的点都归到一个集合里,生成了最小生成树。
根据上图实现的代码如下
1 #include<bits/stdc++.h 2 #define N 7 3 using namespace std; 4 typedef struct _node{ 5 int val; 6 int start; 7 int end; 8 }Node; 9 Node V[N]; 10 int cmp(const void *a, const void *b) 11 { 12 return (*(Node *)a).val - (*(Node*)b).val; 13 } 14 int edge[N][3] = { { 0, 1, 3 }, 15 { 0, 4, 1 }, 16 { 1, 2, 5 }, 17 { 1, 4, 4 }, 18 { 2, 3, 2 }, 19 { 2, 4, 6 }, 20 { 3, 4, 7} 21 }; 22 23 int father[N] = { 0, }; 24 int cap[N] = {0,}; 25 26 void make_set() //初始化集合,让所有的点都各成一个集合,每个集合都只包含自己 27 { 28 for (int i = 0; i < N; i++) 29 { 30 father[i] = i; 31 cap[i] = 1; 32 } 33 } 34 35 int find_set(int x) //判断一个点属于哪个集合,点如果都有着共同的祖先结点,就可以说他们属于一个集合 36 { 37 if (x != father[x]) 38 { 39 father[x] = find_set(father[x]); 40 } 41 return father[x]; 42 } 43 44 void Union(int x, int y) //将x,y合并到同一个集合 45 { 46 x = find_set(x); 47 y = find_set(y); 48 if (x == y) 49 return; 50 if (cap[x] < cap[y]) 51 father[x] = find_set(y); 52 else 53 { 54 if (cap[x] == cap[y]) 55 cap[x]++; 56 father[y] = find_set(x); 57 } 58 } 59 60 int Kruskal(int n) 61 { 62 int sum = 0; 63 make_set(); 64 for (int i = 0; i < N; i++)//将边的顺序按从小到大取出来 65 { 66 if (find_set(V[i].start) != find_set(V[i].end)) //如果改变的两个顶点还不在一个集合中,就并到一个集合里,生成树的长度加上这条边的长度 67 { 68 Union(V[i].start, V[i].end); //合并两个顶点到一个集合 69 sum += V[i].val; 70 } 71 } 72 return sum; 73 } 74 int main() 75 { 76 for (int i = 0; i < N; i++) //初始化边的数据,在实际应用中可根据具体情况转换并且读取数据,这边只是测试用例 77 { 78 V[i].start = edge[i][0]; 79 V[i].end = edge[i][1]; 80 V[i].val = edge[i][2]; 81 } 82 qsort(V, N, sizeof(V[0]), cmp); 83 cout << Kruskal(0)<<endl; 84 return 0; 85 }
标签:Prim,int,Kruskal,距离,算法,详解,集合,顶点,INF From: https://www.cnblogs.com/lizihan00787/p/16627506.html