Question

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

Answer 1

图 有如下参数:
 
边数=8 顶点数=5
 
顶点 顶点 边的权值
v1   v2   6
v1   v3   4
v1   v4   2
v2   v3   5
v2   v4   8
v2   v5   6
v3   v4   5
v4   v5   7

用Kruskal(克鲁斯卡尔)算法,求最小生成树.
 
先将所有边的权值按照从小到大排序:
 
顶点 顶点 边的权值
v1   v4   2
v1   v3   4
v2   v3   5
v3   v4   5
v1   v2   6
v2   v5   6
v4   v5   7
v2   v4   8

然后,每次提取权值最小边,逐步组成最小生成树:
 
(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"

#define MAXEDGE 20
#define MAXVEX 20
#define INF 65535

typedef struct
{
	int arc[MAXVEX][MAXVEX];
	int numVertexes, numEdges;
}MGraph;

typedef struct
{
	int begin;
	int end;
	int weight;
}Edge;   //对边集数组Edge结构的定义

//创建图
void CreateMGraph(MGraph *G)
{
	int i, j;

	G->numEdges=8;     //边数
	G->numVertexes=5;  //顶点数

	for (i = 0; i < G->numVertexes; i++)//初始化图
	{
		for ( j = 0; j < G->numVertexes; 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; i < G->numVertexes; i++)
	{
		for(j = i; j < G->numVertexes; j++)
		{
			G->arc[j][i] =G->arc[i][j];
		}
	}
}

//交换权值 以及头和尾
void Swapn(Edge *edges,int i, int j)
{
	int temp;
	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;
}

//对权值进行排序 (选择排序法)
void sort(Edge edges[],MGraph *G)
{
	int i,j,min;
	for ( i = 0; i < (G->numEdges-1); i++)
    {
        min=i;
        for ( j = i + 1; j < G->numEdges; j++)
        {
            if (edges[min].weight > edges[j].weight)
            {
                min=j;
            }
        }
        if(i != min)
        {
            Swapn(edges, i, min);
        }
    }

	printf("边的权值排序之后:\n");
	for (i = 0; i < G->numEdges; i++)
	{
		printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
	}
}

//查找连线顶点的尾部下标
int Find(int *parent, int f)
{
	while ( parent[f] > 0)
	{
		f = parent[f];
	}
	return f;
}

//生成最小生成树
void MiniSpanTree_Kruskal(MGraph G)
{
	int i, j, n, m;
	int k = 0;
	int parent[MAXVEX]; //定义一数组用来判断边与边是否形成环路

	Edge edges[MAXEDGE]; //定义边集数组,edge的结构为begin,end,weight,均为整型

	//用来构建边集数组并排序
	for ( i = 0; i < G.numVertexes-1; i++)
	{
		for (j = i + 1; j < G.numVertexes; j++)
		{
			if (G.arc[i][j]<INF)
			{
				edges[k].begin = i;
				edges[k].end = j;
				edges[k].weight = G.arc[i][j];
				k++;
			}
		}
	}
	sort(edges, &G); //从小到大排序

	for (i = 0; i < G.numVertexes; i++)
    {
        parent[i] = 0;
    }

	printf("打印最小生成树：\n");
	for (i = 0; i < G.numEdges; 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);
		}
	}
}

int main(void)
{
	MGraph G;
	CreateMGraph(&G);
	MiniSpanTree_Kruskal(G);
	return 0;
}

Answer 2

千山鸟飞绝,万径人踪灭.