【18，6，3】已知一个无向图的顶点集为{V0，V1，…，V7}，其邻接矩阵如下所示：
V0 0 1 0 1 1 0 0 0 V1 1 0 1 0 1 0 0 0 V2 0 1 0 0 0 1 0 0 V3 1 0 0 0 0 0 1 0 V4 1 1 0 0 0 0 1 0 V5 0 0 1 0 0 0 0 0 V6 0 0 0 1 1 0 0 1 V7 0 0 0 0 0 0 0 1
(1) 画出该图的图形；
(2) 给出从V0出发的深度优先遍历序和广度优先遍历序。 答：
深度优先：01254673 广度优先：01324657
31
【19，6，3】已知有向图如右图所示，请给出该图的 （1） 每个顶点的入度和出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表；
（5） 各个强连通分量 答案： （1）： 节点号 入度 出度 1 3 0 2 2 2 3 1 2 4 1 3 5 2 1 6 2 3 （2）：
1 0 1 0 0 1 1 2 1 0 1 1 0 1 3 0 1 0 1 0 1 4 0 1 1 0 1 1 5 1 0 0 1 0 1 6 1 1 1 1 1 0 (3)：
32
（（4）：
（5）：
1：无强连通分量
33
【20，6，3】试利用Dijkstra算法求下图在从顶点A到其它顶点的最短距离及对应的路径，写出计算过程中各步状态。
答： 初始（第0步） 第一步（选C） 第二步(选F) 第三步(选E) 第四步(选G) 第五步(选D) 第六步(选B) 终点 D
P D P D P D 34
P D P D P D P B C D E F G
15 2 12 ∞ ∞ ∞ 0 0 0 15 2 12 10 6 ∞ A A A C C 15 2 12 10 6 16 A A A C C F 15 2 12 10 6 16 A A A C C F 15 2 12 10 6 16 A A A C C F 15 2 12 10 6 15 A A A C C D 15 2 12 10 6 15 A A A C C D 【21，6，3】给出如下图所示的具有7个结点的网G。请：
（1） 画出该网的邻接矩阵；
（2） 采用Prim算法，从4号结点开始，给出该网的最小生成树（画出Prim算法
的执行过程及最小生成树的生成示意图）。
1
答： （1）：
0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 1 2 1 0 0 0 1 0 1 3 0 1 0 0 0 1 1 4 0 0 1 0 0 1 1 5 0 0 0 1 1 0 1 6 1 1 1 1 1 1 0
35
1 6 2 3 7 4 0 5 6 2 5 3 3 2 5 1 4 4