克鲁斯卡尔 (kruskal)算法构造最小生成树.cpp

克鲁斯卡尔算法,求最短路径

//用克鲁斯卡尔 (kruskal)算法构造最小生成树
/*
  Name: 王炽英 
  Copyright: 
  Author: 
  Date: 09-10-04 09:04
  Description: 
*/
#include <stdio.h>
#include<stdlib.h>
#define MAXVEX 30      //最多顶点个数
#define MAXE 100       /*MAXE为最大的边数*/ 
struct edgenode        //邻接点的结构 
{
	int adjvex;                /*邻接点序号*/
	int info;                 /*邻接点信息*/
	struct edgenode *next;    //指向下一个邻接点 
}; 
struct vexnode                //顶点类型 
{
	int data;                 /*结点信息*/
	struct edgenode *link;    //指向第一个结点 
};
struct edges
{
  int bv;    //起始顶点 
  int tv;    //终止顶点 
  int w;     //权值 
};

 
typedef struct edges edgeset[MAXE];
typedef struct vexnode adjlist[MAXVEX];
adjlist g;  //定义全局变量
edgeset ge;   // 定义全局变量,表示的图是按权值从小到大排列的 
int n;    //定义顶点数 
int e;    //定义边数
int set[MAXE];  //记录点与点之间的情况 


void creatgraph()
{
	int i,s,d,m;
	struct edgenode *p,*q;
	printf("输入结点数(n).\n");
	scanf("%d",&n);
	printf("输入边数(e).\n");
	scanf("%d",&e);
	for (i=1;i<=n;i++)
	{
        g[i].data=i;      //初始化结点信息 
		g[i].link=NULL;
	}
	for (i=0;i<e;i++)
	{
		printf("\n第%d条边=>\n起点序号,终点序号,权重:\n",i+1);
		scanf("%d",&s);
	    scanf("%d",&d);
	    scanf("%d",&m);
		p=(struct edgenode *)malloc(sizeof(struct edgenode));
		p->adjvex=d;       //输入邻接点 
		p->info=m;         //输入权重 
		p->next=g[s].link;                    /*p插入顶点s的邻接表中*/
		g[s].link=p;            
	}
}

void travgraph()     //遍历邻接图函数 
{
	int i;
	struct edgenode *p;
	printf("遍历图的结果如下:\n");
	for (i=1;i<=n;i++)
	{
		printf("[%d,%d]=>",i,g[i].data);
		p=g[i].link;
		if(p!=NULL)
		{
         while(p->next!=NULL)
		 {
			printf("(%d,%d)-->",p->adjvex,p->info);
			p=p->next;
		 }
		 printf("(%d,%d)",p->adjvex,p->info);
        }		 
		printf("\n");
	}
}

void input()    //输入g[]的方法 
{
    struct edgenode *p;
    int i,j,k,k1,k2,k3;
    j=1;
    for(i=1;i<=n;i++)    //先输入 
    {
     p=g[i].link;
     while(p!=NULL)    //p非空则输入值 
     {
       ge[j].bv=g[i].data;
       ge[j].tv=p->adjvex;
       ge[j].w=p->info;
       p=p->next;
       ++j;
     }       
    }
    k=0;
    //按权值大小排序 
    for(j=e-1;j>0;j--)  //共有个ge[]型结点进行比较    
    {
      for(i=1;i<e-k;i++)   //每比较一次，下一次比较的次数减1 ，k减1 
      {
        if(ge[i].w>ge[i+1].w)
         {
           k1=ge[i].bv;
           k2=ge[i].tv;
           k3=ge[i].w;
           ge[i].bv=ge[i+1].bv;
           ge[i].tv=ge[i+1].tv;
           ge[i].w=ge[i+1].w;
           ge[i+1].bv=k1; 
           ge[i+1].tv=k2;
           ge[i+1].w=k3; 
         }
      }
      k++;    
    }
   /* printf("按权值大小排序后的结果：\n");
    printf("起点  终点  权值\n");
    for(i=1;i<=e;i++)   //输出按权值大小排序后的结果
   
     printf(" %d     %d     %d \n",ge[i].bv,ge[i].tv,ge[i].w);
   */      
}


int seeks(int &v)    //寻找输入的结点 
{
	int i;
	i=v;
	while(set[i]>0)   //若不为0，则这个点已经存储了与i组成最小的边的另一个结点 
     {
      i=set[i];     //返回set[i]
     }    
	return (i);    //否则返回i 
}

void kruskal()   //克鲁斯卡尔算法 
{
  int v1,v2,i,j;
  for (i=1;i<=n;i++) 
  {
    set[i]=0;               /*给s中的每个元素赋初值，一开始没有存储结点信息*/
  }    
  i=1;                   /*i表示待获取的生成树中的边数,初值为1*/
  j=1;                  /*j表示ge中的下标,初值为1*/
  printf("起点  终点  权值\n");
  while((j<n)&&(i<=e))   /*按边权递增顺序，逐边检查该边是否应加入到生成树中*/
   {
	  v1=seeks(ge[i].bv);    /*确定顶点v所在的连通集*/
	  v2=seeks(ge[i].tv);                         
	  if(v1!=v2)        /*当v1,v2不在同一顶点集合,确定该边应当选入生成树*/
       {
		 printf(" %d     %d     %d \n",ge[i].bv,ge[i].tv,ge[i].w);
		 set[v1]=v2;
		 j++;
       }
    i++;
   }
}
main()
{
  printf("建立图过程如下：\n"); 
  creatgraph();
  travgraph();
  input();   //自动输入ge[]所需要的值，并进行升序排列
  printf("克鲁斯卡尔算法 .\n"); 
  kruskal();
  printf("\n");
  system("pause");  
}