最小生成树
实验内容：
设G=（V，E）是无向图联通带权图，即一个网络。E中每条边（v，w）的权为c[v][w]。如果G的一个子图G’是一棵包含G的所有定点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为最小生成树。采用贪心策略可以直接求得给定网络的最小生成树。
编成任务：
给定网络图，求其最小生成树。
Input
节点个数和给定网络图的邻接矩阵表示方法，其中权值为65535表示两个节点间没有连接。否则数字表示节点间权值。
Output
输出最小生成树包括的节点
Sample Input
11
65535 9 59 69 96 11 72 100 17 43 28
9 65535 40 21 23 61 78 97 41 76 86
59 40 65535 39 48 55 64 11 85 23 44
69 21 39 65535 82 80 62 80 98 8 78
96 23 48 82 65535 70 97 55 2 6 2
11 61 55 80 70 65535 45 71 45 42 45
72 78 64 62 97 45 65535 72 93 89 17
100 97 11 80 55 71 72 65535 97 28 100
17 41 85 98 2 45 93 97 65535 70 77
43 76 23 8 6 42 89 28 70 65535 72
28 86 44 78 2 45 17 100 77 72 65535
Sample Output
106
#include<iostream.h>
int c[100][100];
void prim(int n,int c[100][100]);
int main()
{
int n;
cin>>n;
for(int i1 = 1; i1 <= n; i1++)
for(int i2 = 1; i2 <= n; i2++)
cin>>c[i1][i2];
prim(n,c);
return 0;
}
void prim(int n,int c[100][100])
{
int lowcost[100];
int closest[100];
bool s[100];
s[1]=true;
for(int i=2;i<=n;i++)
{
lowcost[i]=c[1][i];
closest[i]=1;
s[i]=false;
}
int sum=0;
for(int i1=1;i1<n;i1++)
{
int min=65535;
int j=1;
for(int k=2;k<=n;k++)
if((lowcost[k]<min)&&(!s[k]))
{
min=lowcost[k];
j=k;
}
sum=sum+lowcost[j];
//cout<<j<<" "<<closest[j]<<" "<<lowcost[j]<<endl;
s[j]=true;
for(int k1=2;k1<=n;k1++)
if((c[j][k1]<lowcost[k1])&&(!s[k1]))
{
lowcost[k1]=c[j][k1];
closest[k1]=j;
}
}
cout<<sum<<endl;
}
评论1
最新资源