Prim(普里姆)算法求最小生成树的思想及C语言实例讲解

1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
5 6 6
4 6 2

#include<stdo.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];//依附在U中的顶点；标记是否已被选中
  int min;
  int result=0;//记录最短距离权值的和
 
 
  for (i=0;i<vcoun;k++)  //初始化所有数组，把最短距离初始化为其他顶点到1结点的距离
  {
      lowcost[i]=G[0][i]; 
      closeset[i]=0;   
   used[i]=0;  
   father[i]=-1;   
  }  
  used[0]=1;
 
 
  
  for (i=1;i<=vcount-1;i++)   
  {   
   j=0;
    min = infinity;
      
   for (k=1;k<count;k++) //for循环得到离结点最近的顶点j
   if ((!used[k])&&(lowcost[k]
   {
    min = lowcost[k];
    j=k;
   }
   father[j]=closeset[j]; 
   printf("%d %d\n",j+1,father[j]+1);//输出当前找到的结点，该顶点依附的上一个结点
   result=result+G[j][closeset[j]];
   used[j]=1;;//把第j个顶点并入了U中  
   for (k=1;k
        
   if (!used[k]&&(G[j][k]保留到k的最短路径
 
    {
      lowcost[k]=G[j][k];   
      closeset[k]=j;
    }   
  }
  printf("%d",result);
}
        
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_vertexer;i++)
  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;
 
}