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

图 有如下参数:

 

边数=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

}

两个图的顶点集合之间能够建立一一对应的映射，对应的顶点之间保持边的一一对应关系。

也可以通过图的邻接矩阵来探讨。一个图的邻接矩阵经过有限次的互换行或列的变换变成另一个图的邻接矩阵，则两个图同构。

---