最小生成树（kruskal）.c

数据结构学习用到的一些程序！！里面有二叉树相关的几个

//将图中的边按权值从小到大的顺序依次选取，若选取的边使生成树不形成回路，则把它
//并入生成树中，保留作为生成树的边，若形成回路则舍弃

#include <stdio.h>
#include <malloc.h>
#define MAX 20                            //定义节点容量


typedef struct                            //图结构
{                          
	int vexs[MAX];                        //节点数组
	int arcs[MAX][MAX];                   //边数组
	int vexnum,arcnum;                    //节点数，边数
}MGraph;

void create(MGraph *G)                    //图的建立
{                                          
	int i,j;
	int v1,v2,v3;
	printf("输入节点数和边数:\n");                    //输入节点数和边数
	scanf("%d%d",&(G->vexnum),&(G->arcnum));
	for(i=1;i<=G->vexnum;i++)                         //节点初始化为1,2,3...
	{
		G->vexs[i]=i;
	}
    for(i=1;i<=G->vexnum;i++)                         //关系矩阵初始化全为0
		for(j=1;j<=G->vexnum;j++)
			G->arcs[i][j]=0;
    printf("输入各边和权值:\n");
	for(i=1;i<=G->arcnum;i++)                         //输入各边和权值，修改关系矩阵
	{
		printf("边 %d: ",i);
		scanf("%d%d%d",&v1,&v2,&v3);
		G->arcs[v1][v2]=v3;
		G->arcs[v2][v1]=v3;
	}
	printf("结束建立\n");
	for(i=1;i<=G->vexnum;i++)                          //打印关系矩阵（供查错用）
	{
		for(j=1;j<=G->vexnum;j++)
			printf("%4d",G->arcs[i][j]);
	    printf("\n");
	}
	return;
}


void Kruskal(MGraph t)
{      
	int closest[MAX];         //纪录节点在S中的邻接点
	int s[MAX];               //s[]表示节点是否已经加入到了S中                     
    int i,k,m;
	int count=1;              //计数
	int min=100;              //纪录最小值 
	int j=1;
    int l;
	s[1]=1;
	for(i=2;i<=t.vexnum;i++)    //除1外，其余节点标志位为0
	{
		s[i]=0;
	}		
	while(count<t.vexnum)        //选取全最小的一边
	{
		min=100;
		for(k=2;k<=t.vexnum;k++)
			for(l=1;l<=t.vexnum;l++)
			{
				if((t.arcs[l][k]>0)&&(t.arcs[l][k]<min)&&(s[l])&&(!s[k]))
				{
					min=t.arcs[l][k];
				    m=k;
				    closest[m]=l;
				}
			}	
		printf("%d-%d\n",m,closest[m]);
	    s[m]=1;                          //选出一个后，标志位置1
		count++;                           //计数器加一
	}
			
}

void main()
{
	MGraph T;
	create(&T);
	Kruskal(T);
}