#include <stdio.h>  
#include <string.h>  
#include <stdlib.h>  

#define infinity 1000000  
#define max_vertexes 6   
 

typedef int Graph[max_vertexes][max_vertexes];  
 

void prim(Graph G,int vcount,int father[])  
{      
int i,j,k;   
int lowcost[max_vertexes];  
int closeset[max_vertexes],used[max_vertexes];  
int min;    
for (i=0;i<vcount;i++)       
  {  
/* 最短距离初始化为其他节点到1号节点的距离 */     
    lowcost[i]=G[0][i];  
    /* 标记所有节点的依附点皆为默认的1号节点 */  
     closeset[i]=0;        
  used[i]=0;      
    father[i]=-1;        
}      
used[0]=1; /*第一个节点是在s集合里的*/  
/* vcount个节点至少需要vcount-1条边构成最小生成树 */    
  for (i=1;i<=vcount-1;i++)        
   {         
 j=0;  
     min = infinity;  
       /* 找满足条件的最小权值边的节点k */        
     for (k=1;k<vcount;k++)  
         /* 边权值较小且不在生成树中 */       
 if ((!used[k])&&(lowcost[k]<min))   
    {  
              min =  lowcost[k];  
              j=k;  
            }         
    father[j]=closeset[j];     
printf("%d %d\n",j+1,closeset[j]+1);//打印边     
used[j]=1;;//把第j个顶点并入了U中       
for (k=1;k<vcount;k++)  
         /* 发现更小的权值 */         
   if (!used[k]&&(G[j][k]<lowcost[k]))         
{   
                  lowcost[k]=G[j][k];/*更新最小权值*/         
      closeset[k]=j;;/*记录新的依附点*/  
    }        
   }  
}  
                   
int main()  
{  
FILE *fr;  
int i,j,weight;  
Graph G;  
int fatheer[max_vertexes];  
for(i=0; i<max_vertexes; i++)  
for(j=0; j<max_vertexes; j++)  
G[i][j] = infinity;  
fr = fopen("prim.txt","r");  
if(!fr)  
{  
printf("fopen failed\n");  
exit(1);   
}  
while(fscanf(fr,"%d%d%d", &i, &j, &weight) != EOF)  
{  
G[i-1][j-1] = weight;  
G[j-1][i-1] = weight;  
}  
prim(G,max_vertexes,fatheer);  
return 0;  
}  

 邻接矩阵的形式进行存储的实现：

<pre name="code" class="html">#include <stdio.h>  
#define n 6  
#define MaxNum 10000  /*定义一个最大整数*/  
  
/*定义邻接矩阵类型*/  
typedef int adjmatrix[n+1][n+1];   /*0号单元没用*/  
  
typedef struct{  
    int fromvex,tovex;  
    int weight;  
}Edge;  
typedef Edge *EdgeNode;  
  
int arcnum;     /*边的个数*/  
  
/*建立图的邻接矩阵*/  
void CreatMatrix(adjmatrix GA){  
    int i,j,k,e;  
    printf("图中有%d个顶点\n",n);  
    for(i=1;i<=n;i++){  
        for(j=1;j<=n;j++){  
            if(i==j){  
                GA[i][j]=0;         /*对角线的值置为0*/  
            }  
            else{  
                GA[i][j]=MaxNum;    /*其它位置的值置初始化为一个最大整数*/  
            }  
        }  
    }  
    printf("请输入边的个数：");  
    scanf("%d",&arcnum);  
    printf("请输入边的信息，按照起点，终点，权值的形式输入：\n");  
    for(k=1;k<=arcnum;k++){  
        scanf("%d,%d,%d",&i,&j,&e);  /*读入边的信息*/  
        GA[i][j]=e;  
        GA[j][i]=e;  
    }  
}  
  
/*初始化图的边集数组*/  
void InitEdge(EdgeNode GE,int m){  
    int i;  
    for(i=1;i<=m;i++){  
        GE[i].weight=0;  
    }  
}  
  
/*根据图的邻接矩阵生成图的边集数组*/  
void GetEdgeSet(adjmatrix GA,EdgeNode GE){  
    int i,j,k=1;  
    for(i=1;i<=n;i++){  
        for(j=i+1;j<=n;j++){  
            if(GA[i][j]!=0&&GA[i][j]!=MaxNum){  
                GE[k].fromvex=i;  
                GE[k].tovex=j;  
                GE[k].weight=GA[i][j];  
                k++;  
            }  
        }  
    }  
}  
  
/*按升序排列图的边集数组*/  
void SortEdge(EdgeNode GE,int m){  
    int i,j,k;  
    Edge temp;  
    for(i=1;i<m;i++){  
        k=i;  
        for(j=i+1;j<=m;j++){  
            if(GE[k].weight>GE[j].weight){  
                k=j;  
            }  
        }  
        if(k!=i){  
            temp=GE[i];GE[i]=GE[k];GE[k]=temp;  
        }  
    }  
}  
  
/*利用普里姆算法从初始点v出发求邻接矩阵表示的图的最小生成树*/  
void Prim(adjmatrix GA,EdgeNode T){  
    int i,j,k,min,u,m,w;  
    Edge temp;  
    /*给T赋初值，对应为v1依次到其余各顶点的边*/  
    k=1;  
    for(i=1;i<=n;i++){  
        if(i!=1){  
            T[k].fromvex=1;  
            T[k].tovex=i;  
            T[k].weight=GA[1][i];  
            k++;  
        }  
    }  
    /*进行n-1次循环，每次求出最小生成树中的第k条边*/  
    for(k=1;k<n;k++){  
        min=MaxNum;  
        m=k;  
        for(j=k;j<n;j++){  
            if(T[j].weight<min){  
                min=T[j].weight;m=j;  
            }  
        }  
        /*把最短边对调到k-1下标位置*/  
        temp=T[k];  
        T[k]=T[m];  
        T[m]=temp;  
        /*把新加入最小生成树T中的顶点序号赋给j*/  
        j=T[k].tovex;  
        /*修改有关边，使T中到T外的每一个顶点保持一条到目前为止最短的边*/  
        for(i=k+1;i<n;i++){  
            u=T[i].tovex;  
            w=GA[j][u];  
            if(w<T[i].weight){  
                T[i].weight=w;T[i].fromvex=j;  
            }  
        }  
    }  
}  
  
/*输出边集数组的每条边*/  
void OutEdge(EdgeNode GE,int e){  
    int i;  
    printf("按照起点，终点，权值的形式输出的最小生成树为：\n");  
    for(i=1;i<=e;i++){  
        printf("%d,%d,%d\n",GE[i].fromvex,GE[i].tovex,GE[i].weight);  
    }  
}  
  
void main(){  
    adjmatrix GA;  
    Edge GE[n*(n-1)/2],T[n];  
    CreatMatrix(GA);  
    InitEdge(GE,arcnum);  
    GetEdgeSet(GA,GE);  
    SortEdge(GE,arcnum);  
    Prim(GA,T);  
    printf("\n");  
    OutEdge(T,n-1);  
}</pre><br>  
<br>  
<p></p>  
<pre></pre>  
<p></p>