（10 分）下图所示是一带权有向图的邻接表。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：

（1）该带权有向图的图形。 （2）从顶点 V1 为起点的广度优先搜索的顶点序列及对应的生成树。 （3）以顶点 V1 为起点的深度优先搜索生成树。 （4）由顶点 V1 到顶点 V3 的最短路径。 （5）若将该图看成无向图，用 Prim 算法给出图 G 的一棵最小生成树的生成过程。

最小生成树 信号量

[tag_link]

**【解析】** (1) 该邻接表存储对应的带权有向图如下：

(2) 以顶点 $V1$ 为起点的广度优先搜索的顶点序列依次为 $V1,V2,V4,V6,V3,V5$ ，对应的生成树如下：

(3) 生成树：顶点集合 $V(G)=\{V1,V2,V3,V4,V5,V6\}$ ，边的集合 $E(G)=\{(V1,V2),(V2,V3),(V1,V4),(V4,V5),(V5,V6)\}$ 。（图略）

(4) V1 到 V3 最短路径为 67: (V1—V4—V3)。

(5) 从 V1 点开始，第一趟寻找 V1 和点集 $\{V2,V3,V4,V5,V6\}$ 之间的最小权值的边。(V5,V1)。

第二趟寻找点集 $\{V1,V5\}$ 和点集 $\{V2,V3,V4,V6\}$ 之间的最小权值的边。(V5,V6)。

第三趟寻找点集 $\{V1,V5,V6\}$ 和点集 $\{V2,V3,V4\}$ 之间的最小权值的边。(V1,V4)。

第四趟寻找点集 $\{V1,V4,V5,V6\}$ 和点集 $\{V2,V3\}$ 之间的最小权值的边。(V4,V2)。

第五趟寻找点集 $\{V1,V2,V4,V5,V6\}$ 和点集 $\{V3\}$ 之间的最小权值的边。(V2,V3)。

所以最小生成树的边集合为 $\{(V5,V1),(V5,V6),(V1,V4),(V4,V2),(V2,V3)\}$ （图形略）。