最小生成树(prim).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;
}
//算法假设有一个集合S，选中的节点依次加入到S中
void Prim(MGraph g)                                //最小生成树！
{  
	int k=1;                                       //初始加入到S中的节点为1     
	int i,j,t,m;
	int a;
	struct Close                                   //节点之间关系结构定义
	{ 
	int vex;                                       //存放此节点在S中被选中的关系节点
	int lowcost;                                   //存放于S中关系节点的权值
	};
	struct Close closedge[MAX];                    //定义关系结构数组
	for (j=1;j<=g.vexnum;j++)                      //初始令所有节点均与节点1为邻接节点，初始化结构数组
		if (j!=k) 
		{
			closedge[j].vex=1;
		    closedge[j].lowcost=g.arcs[k][j];
		}
	closedge[k].lowcost=-1;                        //节点k被标记
    for (i=2;i<=g.vexnum;i++) 
	{
		for (t=2;t<=g.vexnum;t++)                  //选出第一个S中的节点的邻接节点
			if (closedge[t].lowcost>0)
			{
				a=closedge[t].lowcost;
				k=t;
				break;
			}
		for (m=2;m<=g.vexnum;m++)                     //选出其他的S中的邻接节点，并与前面选出的节点比较权重，选出最小的
			if ((closedge[m].lowcost>0)&&(closedge[m].lowcost<a))
			{
				a=closedge[m].lowcost;                 
			    k=m;                                   //标记出最小权值节点编号
			}
		 
    printf("%d  %d",closedge[k].vex,g.vexs[k]);        //打印此最小权值节点和他在S中的邻接节点
	printf("\n");
	closedge[k].lowcost=-1;                           //次节点被标记
	for (j=2;j<=g.vexnum;j++)
	{
		if (g.arcs[k][j]!=0&&(closedge[j].lowcost==0))//若前面的节点与k前一个被选中的节点不为邻接节点
		{                                             //修改结构数组
			closedge[j].vex=g.vexs[k];
		    closedge[j].lowcost=g.arcs[k][j];
		}
		if (g.arcs[k][j]!=0&&(g.arcs[k][j]<closedge[j].lowcost))//若前面的节点与k前一个被选中的节点为邻接节点
		{                                                       //修改结构数组
			closedge[j].vex=g.vexs[k];
		    closedge[j].lowcost=g.arcs[k][j];
	}
	}
	}
}

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