数据结构第6章图.doc

第6章 图【例6-2】 图G(V，E)，其中V=1,2,3,4,5,6，,，请画出图G，并写出其邻接矩阵和邻接表表示。解：图G如图6-4中的(a)所示，图G的邻接矩阵和邻接表表示分别如图(b)和(c)所示。对于这类问题，只要掌握了图的概念和存储结构就可以做出正确的答案。通常情况下对图的顶点排列顺序和各顶点的邻接点排列顺序并没有特定要求，因此，在写出邻接矩阵和邻接表表示时，只要按照某种排列顺序画出相应的结构图就可以了。但应该注意的是，对于邻接矩阵表示，如果顶点结点的顺序不同，那么邻接矩阵就不相同；对于邻接表表示，如果顶点结点的顺序或者邻接点的顺序不同，那么邻接表就不相同。0 1 1 1 0 00 0 0 0 1 00 1 0 0 1 10 0 0 0 0 10 0 0 0 1 10 0 0 0 0 0(b)图6-4 图及其存储结构1(a)34256(c)126453223545666【例6-3】已知一个无向图的邻接表如图6-5所示，要求：（1）画出该无向图；（2）根据邻接表，分别写出用DFS(深度优先搜索)和BFS（广度优先搜索）算法从顶点V0开始遍历该图后所得到的遍历序列。图6-5 图的邻接表存储V6V0V1V5V3V4V22305604361121210250634解：（1）该无向图如图6-6所示。v0v1v2v3v4v6v5图6-6 无向图（2）根据该无向图的邻接表表示，从顶点V0开始的深度优先遍历序列为：V0、V2、V3、V1、V4、V6、V5。广度优先遍历序列为V0、V2、V5、V6、V1、V3、V4。从图的逻辑结构上来讲，从图中某个顶点开始的深度(或广度)优先遍历序列不一定是唯一的。这是因为在逻辑结构中，并没有对每个顶点的所有邻接点规定它们之间的先后顺序，这样在搜索算法中选取第个邻接点和下一个邻接点时可能会有不同的结果。但是在存储结构中，明确地给出了邻接点的先后顺序，这时深度优先和广度优先遍历序列就是唯一的。【例6-4】对于如图6-8所示的带权无向图，用图示说明：（1）利用Prim算法从顶点a开始构造最小生成树的过程；3e1fdcbag97946218548图6-8 带权无向图（2）利用Kruskal算法构造最小生成树的过程；解：（1）利用Prim算法从顶点a开始构造最小生成树的过程如图6-9所示。aefdcbg初始状态aefdcbg连通e2aefdcbg连通g21aefdcbg连通d2133aefdcbg连通f2143aefdcbg连通b2146图6-9 用Prim算法构造最小生成树的过程3aefdcbg连通c21461（2）利用Kruskal算法构造最小生成树的过程如图6-10所示。aefdcbg初始状态aefdcbg增加第2条边11aefdcbg增加第1条边13aefdcbg增加第5条边21413aefdcbg增加第4条边211aefdcbg增加第3条边211图6-10 用Kruskal算法构造最小生成树的过程3aefdcbg增加第6条边21461三、应用题1. 对于一个无向图6-11(a)，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。注：每一种序列都是唯一的，因为都是在存储结构上得到的。1. 深度优先搜索序列：0,1,2,8,3,4,5,6,7,9 广度优先搜索序列：0,1,4,2,7,3,8,6,5,9 2. 对于一个有向图6-11(b)，假定采用邻接表表示，并且假定每个顶点单链表中的边结点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 注：每一种序列都是唯一的，因为都是在存储结构上得到的。 图6-110165948372(a)603451278(b)2. 深度优先搜索序列：0,4,7,5,8,3,6,1,2 广度优先搜索序列：0,4,3,1,7,5,6,2,83. 已知一个无向图的邻接矩阵如图6-12(a)所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。3. 深度优先搜索序列：0,2,3,5,6,1,4 广度优先搜索序列：0,2,3,5,6,1,4 4. 已知一个无向图的邻接表如图6-12(b)所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。(a) (b)图6-124. 深度优先搜索序列：0,3,6,4,1,5,2 广度优先搜索序列：0,3,2,6,5,4,15. 已知图6-13所示的一个网，按照Prim方法，从顶点1 出发，求该网的最小生成树的产生过程。 (a)V1V2V3V4V5V6V760506540457050524230V1V2V3V4V5V6V750(c)V1V2V3V4V5V6V7(b)5. 过程如图6-16所示 V1V2V3V4V5V6V7504045504230(h)图6-16V1V2V3V4V5V6V75040504230(g)V1V2V3V4V5V6V750405030(f)V1V2V3V4V5V6V75040(d)V1V2V3V4V5V6V7504050(e)6. 已知图6-13所示的一个网，按照Kruskal方法，求该网的最小生成树的产生过程。图6-13V1V2V3V4V5V6V7605065404570505242306. 求解过程如图6-17所示。V1V2V3V4V5V6V7(a)30V1V2V3V4V5V