已知图G的邻接矩阵A= ，试画出它所表示的图G，并根据Prim算法求出图的..._考试资料网

网站首页考试题库热门试题智能家居网课试题

大学试题

题库首页每日一练章节练习

问答题 已知图G的邻接矩阵A= ，试画出它所表示的图G，并根据Prim算法求出图的的最小生成树（给出生成过程）。

参考答案：

（1）图形态：

(2)prim算法求最小生成树:

您可能感兴趣的试卷

你可能感兴趣的试题

1.问答题 如下所示的有向图，回答下面问题：

（1）该图是强连通的吗？若不是，给出强连通分量。
（2）请给出图的邻接矩阵和邻接表表示。

参考答案：

（2）

2.问答题 已知有向图如下所示，请写出该图所有的拓扑序列。

参考答案：拓扑排序如下：
v1, v2, v4, v6, v5, v3, v7, v8 v1, v2, v4, v6, ...

点击查看完整答案

3.问答题 已知图G如下所示，根据Prim算法，构造最小生成树。（要求给出生成过程）

参考答案：

4.问答题 AOE网G如下所示，求关键路径。（要求标明每个顶点的最早发生时间和最迟发生时间，并画出关键路径）

参考答案：

（1）最早发生时间和最迟发生时间：

（2）关键路径：

5.问答题 写出下图中全部可能的拓扑排序序列。

参考答案：

1，5，2，3，6，4
1，5，6，2，3，4
5，1，2，3，6，4
5，1，6，2，3，4
5，6，1，2，3，4

6.问答题 设一个无向图的邻接矩阵如下图所示：
（1）画出该图；
（2）画出从顶点0出发的深度优先生成树；

参考答案：

(1)图形态

(2)深度优先搜索树

7.问答题 已知图G的邻接矩阵如下所示：
（1）求从顶点1出发的广度优先搜索序列；
（2）根据prim算法，求图G从顶点1出发的最小生成树，要求表示出其每一步生成过程。（用图或者表的方式均可）。

参考答案：

(1)广度优先遍历序列：1; 2, 3, 4; 5; 6
(2)最小生成树（prim算法）

8.判断题图的生成树是惟一的。

参考答案：错

9.判断题从源点到终点的最短路径是唯一的。

参考答案：错

10.判断题AOV网是一个带权的有向图。

参考答案：错

点击查看答案解析