最小生成树(prim).c

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

//在图中任取一顶点放入生成树顶点数组中，取出的顶点与图中（除取出的顶点外）顶点找出权值最小的边，
//把该边和顶点放入生成树的边数组和顶点数组中，反复进行这样操作直到所有n个顶点，包含n-1条边都在
//数组中，则得到了最小生成树
#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++)
	{
		G->vexs[i]=i;
	}
    for(i=1;i<=G->vexnum;i++)
		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 Prim(MGraph t)
{
	int lowcost[MAX];         //lowcost[j]是j在S中的一个邻接节点，他与j在S中的其他邻接节点k相比
	int closest[MAX];         //较有c[j][lowcost[j]]<=c[j][k],closest[j]的值就是c[j][lowcost[j]]
	int s[MAX];               //s[]表示节点是否已经加入到了S中                     
    int i,k;
	s[1]=1;
	for(i=2;i<=t.vexnum;i++)
	{
		lowcost[i]=t.arcs[1][i];
		closest[i]=1;
		s[i]=0;
	}
	for(i=1;i<t.vexnum;i++)
	{
		int min=100;
		int j=1;
		for(k=2;k<=t.vexnum;k++)
			if((lowcost[k]>0)&&(lowcost[k]<min)&&(!s[k]))
			{
				min=lowcost[k];
				j=k;
			}
		printf("%d-%d\n",j,closest[j]);
		s[j]=1;
		for(k=2;k<=t.vexnum;k++)
			if((t.arcs[j][k]>0)&&(t.arcs[j][k]<lowcost[k])&&(!s[k]))
			{
				lowcost[k]=t.arcs[j][k];	
				closest[k]=j;
			}
	}
}

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