prim.txt

prim算法是从连通网中的某一个顶点开始

#include<iostream.h>
#define max 99
void prim(int g[max][max],int k,int n)
{
  int i,j,min,p;
  struct{
          int adjvex;
          int lowcost;
        }closedge[30];
  for(i=1;i<=n;i++)
      if(i!=k)
         {
            closedge[i].adjvex=k;
            closedge[i].lowcost=g[k][i];
         }
  closedge[k].lowcost=0;
  for(i=1;i<n;i++)
      {
         p=1;
         min=max;
         for(j=1;j<=n;j++)
            if(closedge[j].lowcost!=0&&closedge[j].lowcost<min)
                {
                   min=closedge[j].lowcost;
                   p=j;
                }
         printf("%d__%d  %d\n",closedge[p].adjvex,p,min);
         closedge[p].lowcost=0;
         for(j=1;j<=n;j++)
            if(g[p][j]<closedge[j].lowcost)
                {
                   closedge[j].lowcost=g[p][j];
                   closedge[j].adjvex=p;
                }
      }
}
void main()
{
  int g[max][max],k,n,i,j;
  cout<<"请输入顶点个数："; cin>>n;
  cout<<"请输入邻接矩阵："<<endl;
  for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
        cin>>g[i][j];
  cout<<"请输入开始顶点："; cin>>k;
  prim(g,k,n);
}