数据结构作业4-图

图数据结构的小练习：

文章目录

• 数据结构作业4-图
• • 3 对图1所示的带权无向图。（40分）
  • • 解：
  • 4 对于图1所示的带权无向图。（20分）
  • • 解：
  • 5 已知带权有向图如下图所示，请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度，给出相应的求解步骤。（20分）
  • • 解：
  • 6 一个AOV网用邻接矩阵表示，如图3，画出该AOV网，扑排序求它的一个拓扑序列，给出相应的步骤。（20分）
  • • 解：

数据结构作业4-图

3 对图1所示的带权无向图。（40分）

① 写出相应的邻接矩阵表示。（10分）

② 写出相应的邻接表表示（邻接链表采用头插法插入边）。（10分）

③ 在邻接表和邻接矩阵存储结构下，分别写出该图从顶点3出发的深度和广度优先遍历序列。（20分）

解：

4 对于图1所示的带权无向图。（20分）

① 按照Prime算法给出从顶点4开始构造最小生成树的过程。

② 按照Kruskal算法给出最小生成树的过程。

解：

5 已知带权有向图如下图所示，请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度，给出相应的求解步骤。（20分）

解：

6 一个AOV网用邻接矩阵表示，如图3，画出该AOV网，扑排序求它的一个拓扑序列，给出相应的步骤。（20分）

解：