mst.c

用普里姆算法借助堆排序实现最短路径的查找

#include "conio.h"
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "string.h"
#include "memory.h"

#define MAX 50
#define MAXSTRL 200
#define MAXISM 99999

typedef struct Node{ //结点
  int vertex;
  int weight;
  struct Node *next;
} Node;

typedef struct {//堆
	 Node * start[MAX+1];
} Graph;

Graph stack;//定义堆

int Adj[MAX+1][MAX+1];  //邻接矩阵　

int vexnum,edgnum;//结点和边数目　
int heapleftnum; //堆中剩佘的结点数
int sum=0;       //放和的地方
char result[MAXSTRL];//放结果和临时字串
char temp[MAXSTRL];
char * str=result;


void Adjut(int p)//对堆，从节点p为根节点的树调整成堆，堆的节点数为heapleftnum
{   
	int work,temp;
	Node * temppoint;
	work=p; //工作变量
	temp=work *2;

	while(temp<=heapleftnum)
	{
		if ( (temp<heapleftnum) && ( (stack.start[temp]->weight)>(stack.start[temp+1]->weight) ) ) //临时节点有右邻且右邻权小于临时节点
		    temp++;//临时节点指向小的
		if (stack.start[temp]->weight>=stack.start[work]->weight)  //临时节点比工作节点权大
			break;//结束排序，
			
		work=temp;	//临时节点比工作节点权小,当前工作结点改为临时节点
		temp=temp*2;	
	}
  	
	if (p!=work) //交换
	 { temppoint=stack.start[p];
	 stack.start[p]=stack.start[work];
	 stack.start[work]=temppoint;
	 }
}

void Heap_sort() //heap sort
{
	int work=(int)(heapleftnum/2);//堆排序工作变量，指向最后一个要排序的堆节点
	while (work>0)           //对从vexnum/2开始到1的节点进行堆基本排序
	 {Adjut(work);work--;}
}


int removeMin() //返回第一个堆节点的号，将第一个堆节点与最后一个节点对换，
{ Node * t;
  t=stack.start[1];
  stack.start[1]=stack.start[heapleftnum];
  stack.start[heapleftnum]=t;
  return (heapleftnum);
}


void main()  //main prostackm
{ 
   int x,y,num,i,j,r,u,t1,t2,t;
   printf("mst\n");
   scanf("%d %d",&vexnum,&edgnum);
 
   //初始化邻接矩阵
   for (i=1;i<=vexnum;i++)
   {
	   for (j=1;j<=vexnum;j++)
		   Adj[i][j]=MAXISM;
   }
   //建立邻接矩阵
   for (i=1;i<=edgnum;i++)
   {
     scanf(" %d %d %d", &x,&y,&num);
     Adj[x][y]=num;
	 Adj[y][x]=num;
   }

   //分配堆空间，初始化堆
   for (i=1;i<=vexnum;i++)
     {stack.start[i]=(Node *)malloc(sizeof(Node));
      stack.start[i]->vertex=i;
	  if (i==1) stack.start[i]->weight=0;
	  else stack.start[i]->weight=MAXISM;
      stack.start[i]->next=NULL;
	  }

   heapleftnum=vexnum;//记录剩余的节点个数

   Heap_sort();//把stack第一次变成堆

   while (heapleftnum!=0)
   { u=removeMin();   //就是把Q中顶端的值弹出付给u,u是堆的序号，不是图的节 点号， 然后再把"堆"中最后一个值放到顶端，
	 heapleftnum--;
     Heap_sort();//然后平衡这个堆
     for (i=1;i<=heapleftnum;i++) 
     if (Adj[stack.start[u]->vertex][stack.start[i]->vertex]!=MAXISM)    //对图G中与u相临的所有边
	   {r=Adj[stack.start[u]->vertex][stack.start[i]->vertex];  //stack[i]->vertex是边e的另一头顶点,r是边e的权值
	   if (r<=(stack.start[i]->weight))  //意思是r 比堆中的i的权小，i的距离就是开始时设的∞
	     if ((r==stack.start[i]->weight) && (stack.start[u]->vertex>stack.start[i]->next->vertex)) {}//如果距里相同，且当前结点序号stack.start[u]->vertex大于结点stack.start[i]->vertex原来指向的结点号stack.start[i]->next->vertex则原连接不变
		 else
		 { stack.start[i]->weight=r;   //把r付给stack.start[i]的权值
           stack.start[i]->next=stack.start[u];    //就是i指向stack.start[u]
	       Heap_sort();                            //然后再平衡一遍这个堆
	     }
	 }
  }

  //输出结果
   for( i=vexnum;i>0;i--)
   {
	    if(stack.start[i]->next!=NULL)
		{
		 t1=stack.start[i]->vertex;
		 t2=stack.start[i]->next->vertex;
		 if(t1>t2)
		 {
			t=t1;
			t1=t2;
			t2=t;
		 } 
	     sprintf(temp,"%d %d %d\n",t1,t2,Adj[t1][t2]);
         str=strcat(str,temp);
	     sum+=Adj[t1][t2];
		}
   }
 

 printf("Cost:%d\n%s",sum,result); 
  //回收堆空间
   for (i=1;i<=vexnum;i++)
     free(stack.start[i]); 
}




/*
while (Q!=空)
{
   u=removeMin(Q);//就是把Q中顶端的值弹出付给u, 然后再把"堆"中最后一个值放到顶端，然后平衡这个堆
   for all e属于 G.incidentEdge(u); 
          // e是图G中与u相临的所有边
   {
      z=G.opposite (u,e) ; //z是边e的另一头顶点
      r=weight(e); //r是边e的权值
      if (r<getdistance(z))  //意思是r 比堆中的z的权小，z的距离就是开始时设的∞。
	  {setdistance(z,r); //把r的权值付给z,
        setparent(u,z);  //就是z的另一顶点设为u,开始时都为Null
        //然后再平衡一遍这个堆；
	  }
   }
}
*/