数据结构习题课第8、7、6章(网上的答案有些有问题的)

第8章 图

8.2 对于如图8.33 所示的无向图，试给出： （1）图中每个顶点的度； （2）该图的邻接矩阵； （3）该图的邻接表； （4）该图的连通分量。

（1） D(V0)=2；D（V1）=2；D（V2）=3；D（V3）=3；D（V4）=2；D（V5）

=1； D(V6)=1.

?0101000??0101000??1010000??1010000??????0101100??0101100???1010100???(2)?邻接矩阵?1010100? ?0011000??0011000??????0000001??0000001??0000010????0000010???v?V（3）邻接表

(4)连通分量 1：

2：

8.5 图8.35 所示的是某个无向图的邻接表，试： （1）画出此图；

（2）写出从顶点A 开始的DFS 遍历结果； （3）写出从顶点A 开始的BFS 遍历结果。

（1）图8.35 邻接表对应的无向图如图8.35.1 所示

（2）

从顶点A 开始的DFS 遍历，深度优先遍历的基本思想：对于给定的图 G=（V,E），首先将V中每一个顶点都标记为未被访问，然后，选取一个源点v?V将v标记为被访问，再递归地用深度优先搜索方法，依次搜索v的所有邻接点w.若w未曾访问过，则以w为新的出发点继续深度优先搜索遍历，如果从v出发所有路的顶点都已被访问过，则结束。 A，B，C，F，E，G，D

从顶点A 开始的BFS 遍历，基本思想：对于给定的图G=（V,E），从图中某未访问过的顶点vi出发：

1）访问顶点vi；

2）访问 vi 的所有未被访问的邻接点w1 ,w2 , …wk ；

3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问； A，B，C，D，F，E，G

8.8 对如图8.36 所示的连通图，分别用Prim 和Kruskal算法构造其最小生成树。

解：（1）Prime 算法的基本思路、步骤P167 Prim算法的基本步骤如下： （1）初始化：U={u0}，TREE={};

（2）如果U=V（G），则输出最小生成树T，并结束算法；

（3）在所有两栖边中找一条权最小的边（u，v）（若候选两栖边中的最小边不止一条，可任选其中的一条），将边（u，v）加入到边集TREE中，并将顶点v并入集合U中。

（4）由于新顶点的加入，U的状态发生变化，需要对U与V-U之间的两栖边进行调整。 （5）转步骤（2）

Prim

算

法

构

造

最

小

生

成

树

过

程

：

（2）采用Kruskal 算法求解最小生成树时首先要对边进行由小到大进行排序，本题对边进行排序的结果是：（D,F）1、（C,F）2、（A,F）3、（A,C）4、（F,G）4、（D,E）4、（D,B）4、（C,D）5、（E,G）5、（A,D）6、（D,G）6、（A,B）7 。根据Kruskal 算法，构造最小生成树的过程如图