第8章 图
对于如图 所示的无向图，试给出： （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：
图 所示的是某个无向图的邻接表，试： （1）画出此图；
（2）写出从顶点A 开始的DFS 遍历结果； （3）写出从顶点A 开始的BFS 遍历结果。
（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
对如图 所示的连通图，分别用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 算法，构造最小生成树的过程如图
对于如图 所示的有向网，用Dijkstra 方法求从顶点A 到图中其他顶点的最短路径，并写出执行算法过程中距离向量d 与路径向量p 的状态变化情况。
解：
Dijkstra算法的基本思想：
把图中所有顶点分成两组，第一组包括已确定最短路径的顶点，初始时只含有一个源点，记为集合S；第二组包括尚未确定最短路径的顶点，记为V-S。按最短路径长度递增的顺序逐个把V-S中的顶点加到S中去，直至从v0出发可以到达的所有顶点都包括到S中。在这个过程中，总保持从v0到第一组（S）各顶点的最短路径都不大于从v0到第二组（V-S）的任何顶点的最短路径长度，第二组的顶点对应的距离值是从v0到此顶点的只包括第一组（S）的顶点为中间顶点的最短路径长度。对于S中任意一点j，v0到j的路径长度皆小于v0到（V-S）中任意一点的路径长度。
(后面四行需要在集合S加上E)
从表中可以看出源点A 到其它各顶点的最短距离及路径为： A→B：48 路径：A→B
A→C：57 路径：A→D→F→C A→D：15 路径：A→D A→E：28 路径：A→E A→F：48 路径：A→D→F A→G：38 路径：A→D→G
数据结构习题课第8、7、6章(网上的答案有些有问题的)
