prim算法求无向图的最小生成树.doc

文档介绍：用Prim算法求无向图的最小生成树
该图用邻接矩阵表示,邻接表原理与之相同。
图1:输入示例
图二:输入时若两点之间没有公共边,则将权值设置为-1。程序设置处理的最大点数为10。
图三:注意到Prim算法的解答结果有时候不是唯一的,这个结果和对图遍历时的顺序有关,但是必需注意的是所有的最小生成树其网络代价和是一样的。
下面是源代码:
/*

Copyright (c) 2002, 2006 by ctu_85
All Rights Reserved.
*/
/* The impact of the situation of articulation point exists can be omitted in Prim algorithm but not in Kruskal algorithm */
#include ""
#define maxver 10
#define maxright 100
int main()
{
int G[maxver][maxver],in[maxver]={0},path[maxver][2];
int i,j,k,min=maxright;
int v1,v2,num,temp,status=0,start=0;
restart:
printf("Please enter the number of vertex(s) in the graph:\n");
scanf("%d",&num);
if(num>maxver||num<0)
{
printf("Error!Please reinput!\n");
goto restart;
}
for(j=0;j<num;j++)
for(k=0;k<num;k++)
{
if(j==k)
G[j][k]=maxright;
else
if(j<k)
{
re:
printf("Please input the right between vertex %d and vertex %d,if no edge exists please input -1:\n",j+1,k+1);
scanf("%d",&temp);
if(temp>=maxright||temp<-1)
{
printf("Invalid input!\n");
goto re;
}
if(temp==-1)
temp=maxright;
G[j][k]=G[k][j]=temp;
}
}
for(j=0;j<num;j++)
{
status=0;
for(k=0;k<num;k++)
if(G[j][k]<maxright)
{
status=1;
break;
}
if(status==0)
break;
}
do
{
printf("Please enter the vertex where Prim algorithm start