【数据结构】树和图01——最小生成树

/最小生成树/

假设需要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。

这时，自然需要考虑这样一个问题，即如何在最节省经费的前提下建立这个通信网。

现在，需要选择一棵生成树，使总的耗费最小。

1.输入
输入的第一行包含一个正整数n，表示图中共有n个顶点。

其中n不超过50。

以后的n行中每行有n个用空格隔开的整数，对于第i行的第j个整数，如果不为0，则表示第i个顶点和第j个顶点有直接连接且代价为相应的值，0表示没有直接连接。

当i和j相等的时候，保证对应的整数为0。

输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图，且保证图中只有一个连通分量。

2.输出
只有一个整数，即最小生成树的总代价。

样例输入
6
0 6 1 5 0 0
6 0 5 0 3 0
1 5 0 5 6 4
5 0 5 0 0 2
0 3 6 0 0 6
0 0 4 2 6 0
样例输出
0->2:1
2->5:4
5->3:2
2->1:5
1->4:3
lowcost:15

#include
#define max 100
#define maxcost 1000000
int prim(int graph[][max],int n)
{
	int lowcost[max];//记录每一个节点到其他点的权值，0为访问过的，maxcost为没有通路 
	int sum=0;
	int i;
	for(i=1;i<n;i++)
	{
		lowcost[i]=graph[0][i];
	}
	int min,minl;
	int j;
	for(i=1;i<n;i++)//每一个节点都遍历一下 
	{
		min=maxcost;//最小权值 
		minl=0;//最小权值的点 
		for(j=1;j<n;j++)
		{
			if(lowcost[j]<min&&lowcost[j]!= 0)
			{
				min=lowcost[j];
				minl=j;
			}
		}//寻找最小权值的点 
		
		sum+=min;
		for(int t=0;t<n;t++)
		if(graph[t][minl]==min)
			printf("%d->%d:%d \n",t,minl,min);
		lowcost[minl]=0;
		
		for(j=0;j<n;j++) 
		{
			if(graph[minl][j]<lowcost[j])
			{
				lowcost[j]=graph[minl][j];
			}
		}//更新lowcost数组 
	}
	return sum;
}
int main()
{
	int n;
	scanf("%d",&n);
	int graph[max][max];
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			scanf("%d",&graph[i][j]);
			if(graph[i][j]==0)
			graph[i][j]=maxcost;
		}//读入无向图的邻接矩阵 
	printf("lowcost:%d",prim(graph,n));
	return 0;
}