下面是一个有5个节点的图各节点之间的边及权值如图所示试用K方法求这个图的最小支撑树画出图并求出其长度

两道题，求详细过程，讲解的。

数据结构算法 试题 急！ 试构造下图的最小生成树，要求分步给出构造过程。

图有如下参数:

边数=8顶点数=5

顶点顶点边的权值
v1v26
v1v34
v1v42
v2v35
v2v48
v2v56
v3v45
v4v57
用Kruskal(克鲁斯卡尔)算法,求最小生成树.

先将所有边的权值按照从小到大排序:

顶点顶点边的权值
v1v42
v1v34
v2v35
v3v45
v1v26
v2v56
v4v57
v2v48
然后,每次提取权值最小边,逐步组成最小生成树:

(1)取最小边(v1,v4,2)
v1--v4
(2)取边(v1,v3,4),不会产生环路.
v1--v4
|
|
v3
(3)取边(v2,v3,5),不会产生环路.
v1--v4
|
|
v3--v2
(4)如果取边(v3,v4,5),会产生环路,所以不能取.
如果取边(v1,v2,6),会产生环路,所以不能取.
取边(v2,v5,6),不会产生环路.
v1--v4
|
|
v3--v2--v5
这就是最小生成树,连通了所有顶点,总权值最小.

顶点边的权值
(v1,v4)2
(v1,v3)4
(v2,v3)5
(v2,v5)6
//C语言测试程序
//最小生成树Kruskal(克鲁斯卡尔)算法
#include"stdio.h"
#defineMAXEDGE20
#defineMAXVEX20
#defineINF65535
typedefstruct
{
	intarc[MAXVEX][MAXVEX];
	intnumVertexes,numEdges;
}MGraph;
typedefstruct
{
	intbegin;
	intend;
	intweight;
}Edge;//对边集数组Edge结构的定义
//创建图
voidCreateMGraph(MGraph*G)
{
	inti,j;
	G->numEdges=8;//边数
	G->numVertexes=5;//顶点数
	for(i=0;inumVertexes;i++)//初始化图
	{
		for(j=0;jnumVertexes;j++)
		{
			if(i==j)
				G->arc[i][j]=0;
			else
				G->arc[i][j]=G->arc[j][i]=INF;
		}
	}
	G->arc[0][1]=6;
	G->arc[0][2]=4;
	G->arc[0][3]=2;
	G->arc[1][2]=5;
	G->arc[1][3]=8;
	G->arc[1][4]=6;
	G->arc[2][3]=5;
	G->arc[3][4]=7;
	for(i=0;inumVertexes;i++)
	{
		for(j=i;jnumVertexes;j++)
		{
			G->arc[j][i]=G->arc[i][j];
		}
	}
}
//交换权值以及头和尾
voidSwapn(Edge*edges,inti,intj)
{
	inttemp;
	temp=edges[i].begin;
	edges[i].begin=edges[j].begin;
	edges[j].begin=temp;
	temp=edges[i].end;
	edges[i].end=edges[j].end;
	edges[j].end=temp;
	temp=edges[i].weight;
	edges[i].weight=edges[j].weight;
	edges[j].weight=temp;
}
//对权值进行排序(选择排序法)
voidsort(Edgeedges[],MGraph*G)
{
	inti,j,min;
	for(i=0;i<(G->numEdges-1);i++)
{
min=i;
for(j=i+1;jnumEdges;j++)
{
if(edges[min].weight>edges[j].weight)
{
min=j;
}
}
if(i!=min)
{
Swapn(edges,i,min);
}
}
	printf("边的权值排序之后:\n");
	for(i=0;inumEdges;i++)
	{
		printf("(%d,%d)%d\n",edges[i].begin,edges[i].end,edges[i].weight);
	}
}
//查找连线顶点的尾部下标
intFind(int*parent,intf)
{
	while(parent[f]>0)
	{
		f=parent[f];
	}
	returnf;
}
//生成最小生成树
voidMiniSpanTree_Kruskal(MGraphG)
{
	inti,j,n,m;
	intk=0;
	intparent[MAXVEX];//定义一数组用来判断边与边是否形成环路
	Edgeedges[MAXEDGE];//定义边集数组,edge的结构为begin,end,weight,均为整型
	//用来构建边集数组并排序
	for(i=0;i	{
		for(j=i+1;j		{
			if(G.arc[i][j]			{
				edges[k].begin=i;
				edges[k].end=j;
				edges[k].weight=G.arc[i][j];
				k++;
			}
		}
	}
	sort(edges,&G);//从小到大排序
	for(i=0;i{
parent[i]=0;
}
	printf("打印最小生成树：\n");
	for(i=0;i	{
		n=Find(parent,edges[i].begin);
		m=Find(parent,edges[i].end);
		if(n!=m)//假如n与m不等，说明此边没有与现有的生成树形成环路
		{
			parent[n]=m;	//将此边的结尾顶点放入下标为起点的parent中
							//表示此顶点已经在生成树集合中
			printf("(%d,%d)%d\n",edges[i].begin,edges[i].end,edges[i].weight);
		}
	}
}
intmain(void)
{
	MGraphG;
	CreateMGraph(&G);
	MiniSpanTree_Kruskal(G);
	return0;
}

最小生成树算法源程序