数据结构与算法 ~ 图 ~ 最小生成树 ~ 普里姆算法（图采用邻接矩阵方式存储）

/*graph--prim*/
#include<stdlib.h>
#include<stdio.h>
#define MAX 10
struct vexnode{
	int visited;/*顶点访问标志*/
}vex[MAX];
int array[MAX][MAX];/*存放权值*/
int vexnum=-1;

/*创建图的邻接矩阵*/
void create(){
 int source,destination,weight,max;
 int i,j;
 for(i=0;i<MAX;i++)
    for(j=0;j<MAX;j++)  array[i][j]=0;
 printf("\n===create Graph===\n");
 printf("\n请输入弧的信息：起点 终点 权值(exit for -1):");
 scanf("%d%d%d",&source,&destination,&weight);
 while (source!=-1){
	 array[source][destination]=weight;
	 array[destination][source]=weight;
	 max=(source>destination)?source:destination;
	 if (max>vexnum)   
		 vexnum=max;
	 printf("\n请输入弧的信息：起点 终点 权值(exit for -1):");
	 scanf("%d%d%d",&source,&destination,&weight);
    }/*while*/
  printf("\n===create over===\n");
}/*create*/

void Print(){
 int i,j,k;
 printf("\n===当前图====");
 printf ("\n   array  :");
 for(i=0;i<=vexnum;i++)  printf("%8d",i);
 printf("\n");
 for(i=0;i<=vexnum;i++){
   printf("%10d:",i);
   for(j=0;j<=vexnum;j++)  
	   printf("%8d",array[i][j]);
   printf("\n");
  }
 printf("\n===图的输出结束====");
}

void prim(){
 int i,j;
 int edgenum=0,sum=0;
 int tempi,tempj,min=999;
 for(i=0;i<=vexnum;i++)
    vex[i].visited=0;/*设置所有顶点均未被访问*/
 printf("\n===普里姆算法:");
 for(i=0;i<=vexnum;i++)/*查找图中的第一条最小边*/
    for(j=0;j<=vexnum;j++)
      if (array[i][j]!=0&&array[i][j]<min){
           min=array[i][j];
           tempi=i;tempj=j;
         }
 printf("[%d,%d](%d)==>",tempi,tempj,array[tempi][tempj]);
 sum+=array[tempi][tempj];
 vex[tempi].visited=1;
 vex[tempj].visited=1;
 edgenum++;
 while(edgenum<vexnum-1){
   min=999;
   /*查找下一条的最小边*/
   for(i=0;i<=vexnum;i++) {
      if (vex[i].visited==0) 
		  continue;/*此边应从已访问的结点出发*/
      for(j=0;j<=vexnum;j++)
		  if (array[i][j]==0||vex[j].visited==1)
			  continue;/*连接到未访问的顶点*/
		  else if (array[i][j]<min){
			  min=array[i][j];
			  tempi=i;tempj=j;
	   }/*if*/
    }/*for*/
   printf("[%d,%d](%d)==>",tempi,tempj,array[tempi][tempj]);
   sum+=array[tempi][tempj];
   vex[tempj].visited=1;/*标志为已访问*/
   vex[tempj].visited=1;
   edgenum++;
  }/*while*/
printf("普里姆结束\n");
printf("权值之和是%d",sum);
}/*prim*/

main(){
  create();
  Print();
  prim();
  system("pause");
  exit(0);
}/*main*/

运行结果是：

===create Graph===

请输入弧的信息：起点 终点 权值(exit for -1):1 2 6

请输入弧的信息：起点 终点 权值(exit for -1):1 3 1

请输入弧的信息：起点 终点 权值(exit for -1):1 4 5

请输入弧的信息：起点 终点 权值(exit for -1):2 3 5

请输入弧的信息：起点 终点 权值(exit for -1):3 4 5

请输入弧的信息：起点 终点 权值(exit for -1):2 5 3

请输入弧的信息：起点 终点 权值(exit for -1):3 5 6

请输入弧的信息：起点 终点 权值(exit for -1):3 6 4

请输入弧的信息：起点 终点 权值(exit for -1):4 6 2

请输入弧的信息：起点 终点 权值(exit for -1):5 6 6

请输入弧的信息：起点 终点 权值(exit for -1):-1 -1 -1

===create over===

===当前图====
   array  :       0       1       2       3       4       5       6
         0:       0       0       0       0       0       0       0
         1:       0       0       6       1       5       0       0
         2:       0       6       0       5       0       3       0
         3:       0       1       5       0       5       6       4
         4:       0       5       0       5       0       0       2
         5:       0       0       3       6       0       0       6
         6:       0       0       0       4       2       6       0

===图的输出结束====
===普里姆算法:[1,3](1)==>[3,6](4)==>[6,4](2)==>[3,2](5)==>[2,5](3)==>普里姆结束
权值之和是15
请按任意键继续. . .