wfj.cpp

避圈算法演示程序

#include "stdlib.h"        /* For _MAX_PATH definition */
#include "stdio.h"
#include "malloc.h"
#include "conio.h"
#include "ctype.h"
#include "iostream.h"

#define MAX  50
int n,c[100][100];
void prim()
{
  int i,j,k,min;
  int *lowcost;
  int *closest;
  int *s;
  
  lowcost=(int*)malloc(sizeof(int)*(n+1));
  closest=(int*)malloc(sizeof(int)*(n+1));
  s=(int*)malloc(sizeof(int)*(n+1));
  s[1]=1;
  
  for(i=2;i<=n;i++)
  {
    lowcost[i]=c[1][i];
    closest[i]=1;
    s[i]=0;
  }
  for(i=1;i<n;i++)
  {
    min=MAX;
    j=1;
    
	for(k=2;k<=n;k++)
       if((lowcost[k]<min)&&(!s[k]))
	   {
          min=lowcost[k];
          j=k;
	   }
     
	   cout<<"("<<j<<","<<closest[j]<<")"<<"      "<<"成本为：";
	   if(j>closest[j])
	   {
		   cout<<c[closest[j]][j];
	   }
	    if(j<closest[j])
		{
			cout<<c[j][closest[j]];
		}
		cout<<endl;
	
		s[j]=1 ;
    
	for(k=2;k<=n;k++)
      if((c[j][k]<lowcost[k])&&(!s[k]))
	  {
         lowcost[k]=c[j][k];
         closest[k]=j;
	  }
  }
}

void main()
{
   int i,j;
   cout<<"**************利用Prim算法得出的最小生成树的边如下**************"<<endl;
   cout<<"输入时，如果两点之间没有连接边请输入一个比所有权值都大的数表示‘无穷大’"<<endl<<endl;
   cout<<"请输入图中节点的个数：";
   cin>>n;
   cout<<endl<<endl<<"你输入的节点个数为：";
   cout<<"请输入的图中各边的权值："<<endl;
   
   for(i=1;i<=n;i++)
    for(j=i+1;j<=n;j++)
	{
      cout<<"    边("<<i<<"，"<<j<<")的权值：";
      cin>>c[i][j];
	}
	cout<<endl<<endl<<"**************<<""利用Prim算法得出的最小生成树的边如下**************"<<endl;
    prim();
	getch();
 
}