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

				//用克鲁斯卡尔 (kruskal)算法构造最小生成树
				/*
				  Name: 王炽英 
				  Copyright: 
				  Author: 
				  Date: 09-10-04 09:04
				  Description: 
				*/
				#include 
				#include
				#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					{
				        g[i].data=i;      //初始化结点信息 
						g[i].link=NULL;
					}
					for (i=0;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					{
						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				    {
				     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				      {
				        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				   
				     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				  {
				    set[i]=0;               /*给s中的每个元素赋初值，一开始没有存储结点信息*/
				  }    
				  i=1;                   /*i表示待获取的生成树中的边数,初值为1*/
				  j=1;                  /*j表示ge中的下标,初值为1*/
				  printf("起点  终点  权值\n");
				  while((j				   {
					  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");  
				}