Prim算法是构造图的最小邻接矩阵的常用算法之一。设图为无向图，用邻接矩阵来存储。

以下面的图为例，左边为无向图，右边为其最小生成树：

http://s8/middle/686d0fb0nb77fbffcf217&690Prim算法" TITLE="C语言编制最小生成树 Prim算法" />

整个程序如下：

#include<stdio.h>
#define maxsize 1000 //表示顶点间不可达
#define n 6   //连通网络的结点数
typedef struct
{
 int formvex,endvex;//边的起点和终点
 int length;//边的权值
}edge;

void prim(int dist[][n],edge T[]);//从第一个定点出发构造连通网络dist的最小生成树，结果放在T中

void main()
{
 printf("                           ——Prim算法——\n");
 int dist[n][n]={
 {maxsize,6,1,5,maxsize,maxsize},
 {6,maxsize,5,maxsize,3,maxsize},
 {1,5,maxsize,7,5,4},
 {5,maxsize,7,maxsize,maxsize,2},
 {maxsize,3,5,maxsize,maxsize,6},
 {maxsize,maxsize,4,2,6,maxsize}
 };//连通网络的带权邻接矩阵
 edge T[n-1];//生成树
 prim(dist,T);
 int i,j;
 printf("【输出连通网络的带权邻接矩阵】\n");
 for(i=0;i<n;i++)
 {
  for(j=0;j<n;j++)
   printf("\t%d",dist[i][j]);
  printf("\n");
 }
 printf("【输出最小生成树的边及权】\n");
 for(i=0;i<n-1;i++)
 {
  printf("\t(%d,%d) %d\n",T[i].formvex,T[i].endvex,T[i].length);
 }
}

void prim(int dist[][n],edge T[])//从第一个定点出发构造连通网络dist的最小生成树，结果放在T中
{
 int j,k,m,v,min,max=10000;
 int d;
 edge e;
 for(j=1;j<n;j++)  //构造初始候选紫边集
 {
  T[j-1].formvex=1;  //顶点1是第一个加入树中的红点
  T[j-1].endvex=j+1;
  T[j-1].length=dist[0][j];
 }
 for(k=0;k<n-1;k++)//求第k条边
 {
  min=max;
  for(j=k;j<n-1;j++)//在候选紫边集中找出最短紫边
  {
   if(T[j].length<min)
   {
    min=T[j].length;
    m=j;
   }//T[m]是当前最短紫边
  }
  e=T[m];T[m]=T[k];T[k]=e;//T[k]和T[m]交换后，T[k]是第k条红色树边
  v=T[k].endvex;//v是新红点
  for(j=k+1;j<n-1;j++)//调整候选紫边集
  {
   d=dist[v-1][T[j].endvex-1];
   if(d<T[j].length)
   {
    T[j].length=d;
    T[j].formvex=v;
   }
  }
 }
}//prim

运行结果：

http://s10/middle/686d0fb0nb77fc2f9c789&690Prim算法" TITLE="C语言编制最小生成树 Prim算法" />