题目

图G=<V, E>,其中V=( a, b, c, d, e),E=( (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) ),对应边的权值依次为2、1、2、3、6、1、4及5,试(1)画出G的图形; (2)写出G的邻接矩阵;(3)求出G权最小的生成树及其权值.

图G=<V, E>,其中V={ a, b, c, d, e},E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) },对应边的权值依次为2、1、2、3、6、1、4及5,试

(1)画出G的图形; (2)写出G的邻接矩阵;

(3)求出G权最小的生成树及其权值.

题目解答

答案

解:

(1)

(2)

(3)

其中权值是:7

解析

步骤 1：画出图G的图形
根据题目中给出的顶点和边的信息，我们可以画出图G的图形。顶点为a, b, c, d, e，边为(a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e)，对应边的权值依次为2、1、2、3、6、1、4及5。
步骤 2：写出G的邻接矩阵
邻接矩阵是一个二维数组，其中A[i][j]表示顶点i和顶点j之间的边的权值。如果顶点i和顶点j之间没有边，则A[i][j]为0。
步骤 3：求出G权最小的生成树及其权值
使用Kruskal算法或Prim算法求出最小生成树。Kruskal算法是将边按权值从小到大排序，然后依次加入生成树中，直到生成树包含所有顶点。Prim算法是从任意一个顶点开始，每次选择与当前生成树相连的最小权值的边加入生成树，直到生成树包含所有顶点。