习题6-5 最小生成树
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。已知村庄数N和可建道路数M，设初始状态下任意村庄之间没有路，请编写程序，根据输入的两村庄间修建道路的费用情况，计算这些村庄畅通所需要的最低成本。
输入格式:
测试数据有多组。每组测试数据第1行输入村庄数目N ( 1< N < 11 )和道路数M；随后的M行输入村庄间道路的成本，每行给3个正整数，分别是两个村庄的编号（从1编号到N），修建此两村庄间道路的成本（不超过50）。当输入0 0时，表示输入结束。
输出格式:
对于每组测试，输出这些村庄畅通所需要的最低成本。
输入样例:
3 3
1 2 1
1 3 2
2 3 4
0 0
输出样例:
3
出处:
HDOJ
代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
解题代码
#include<bits/stdc++.h>
using namespace std;
int n;
struct MAP{
int Gmap[50][50];
}G;//创建图
//获取此时dist中最短的路径节点
int getMinPoint(int *dist,bool *visited)
{
int k=-1,min=INT_MAX;
for(int i=1;i<=n;i++){
if(dist[i]<min&&visited[i]==false){
k=i;
min=dist[i];
}
}
return k;
}
//prime算法
void prime(int t){
bool visited[n+1];
int dist[n+1];
int adjvex[n+1];
for(int i=1;i<=n;i++){
dist[i]=G.Gmap[t][i];
visited[i]=false;
if(G.Gmap[t][i]<INT_MAX) adjvex[i]=t;
else adjvex[i]=-1;
}
int k;
visited[t]=true;
dist[t]=0;//初始起点位置要置为0
for(int i=1;i<n;i++){
k=getMinPoint(dist,visited);
visited[k]=true;
for(int j=1;j<=n;j++){
if(dist[j]>G.Gmap[k][j]&&!visited[j]){
dist[j]=G.Gmap[k][j];
adjvex[j]=k;
}
}
}
int ans=0;//求和得出结果。
for(int i=1;i<=n;i++){
ans+=dist[i];
}
cout<<ans<<endl;
}
int main()
{
int m,a,b,w;
while(cin>>n>>m&&n!=0&&m!=0){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
G.Gmap[i][j]=INT_MAX;
}
}
for(int i=0;i<m;i++){
cin>>a>>b>>w;
G.Gmap[a][b]=w;
G.Gmap[b][a]=w;
}
prime(1);
}
}
解题思路
按照prime算法的思路，假设我们有这样一张连通图，如下：
那么我们创建邻接表的时候，就应该的得到如下表一样的结果：
| 坐标 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | INT_MAX | 7 | INT_MAX | INT_MAX | 2 | 1 |
| 2 | 7 | INT_MAX | 4 | INT_MAX | 8 | INT_MAX |
| 3 | INT_MAX | 4 | INT_MAX | 7 | 7 | INT_MAX |
| 4 | INT_MAX | INT_MAX | 7 | INT_MAX | 5 | 5 |
| 5 | 2 | 8 | 7 | 5 | INT_MAX | 3 |
| 6 | 1 | INT_MAX | INT_MAX | 5 | 3 | INT_MAX |
我们的算法prim算法的思想核心就是生成一个顶点集合G={U},然后初始集合添加起始顶点U，在图中找到以U为起点的最近的一条边，将终点加入到集合G中，然后再以集合中的顶点为起点的所有路径中找最短边且不再集合中（不形成环路）的点加入集合，依次类推，直至加入所有顶点。
举例：
起始G={1}；
我们根据邻接表和绘制的图，可以看出，最近的是6，我们将6加入到集合，得到G={1,6};
我们看1和6，他们的最小边是（1，5）这一条边，那么我们将5加入到集合G，得到G={1,6,5}
继续可以看到最短边为（5，6）但是，两个顶点都在集合中，形成了环路，不可取，于是取（5，4），因为最小二叉树形态不唯一，所以也可以取（6，4），一般取小。得到G={1,6,5,4}
然后（1，2），（5，3），（4，3）都为7，那么取小原则，就取（1，2）得到G={1,6,5,4.2}
最有一个节点三，取短的就是（2，3）了，得到G={1,6,5,4,2,3},最终我们得到一个最小二叉树乳如下：
代码中void prime(int t)函数，有三个数组，bool visited记录是否已将这个节点加入集合。int dist集合中连通的最短路径。int adjvex存储节点的上一跳节点。
假设初始t=1
我们的dist数组初始化为INT_MAX,最大整数，然后visited设置为false，都没有找过，可以得到如下的数组：
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| dist | 0 | 7 | INT_MAX | INT_MAX | 2 | 1 |
| visited | true | false | false | false | false | false |
| adjvex | -1 | 1 | -1 | -1 | 1 | 1 |
这里dist[1]一定要是0，因为是起点，并不加入求代价的计算，所以要0.
然后我们调用了函数getMinPoint(dist,visited)，就是找当前的dist中最短的路径，然后返回最短路径的终点，前提是这个点不在我们的集合里，k等于返回的值
k=getMinPoint(dist,visited);
visited[k]=true;
然后我们这里应该就得到k=6；将visited[6]=true;
去找6的所有路径中，小于当前dist的路径信息，修改dist，得到如下表：
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| dist | 0 | 7 | INT_MAX | 5 | 2 | 1 |
| visited | true | false | false | false | false | true |
| adjvex | -1 | 1 | -1 | 6 | 1 | 1 |
for(int j=1;j<=n;j++){
if(dist[j]>G.Gmap[k][j]&&!visited[j]){
dist[j]=G.Gmap[k][j];
adjvex[j]=k;
}
}
然后同样调用getMinPoint(dist,visited);一直重复直至所有的节点都调用完了，执行了n-1次后，得到如下表所示的结果：
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| dist | 0 | 7 | 4 | 5 | 2 | 1 |
| visited | true | true | true | true | true | true |
| adjvex | -1 | 1 | 2 | 5 | 1 | 1 |
文章来源：https://www.toymoban.com/news/detail-486448.html
思路差不多这个思路，大家可以带一下值进去就好理解了，这里我就不多说了，如果有问题请及时指出！文章来源地址https://www.toymoban.com/news/detail-486448.html
到了这里，关于C++数据结构——习题6-5 最小生成树（Prim算法）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
