第七章图

第七章图内容摘要：

t(w)。 EnQueue(Q, w)。 // 访问的顶点 w入队列 } // if } // while } //if } // BFSTraverse 例如 ， 对图 813所示无向图 G7， 从顶点 1出发的广度优先搜索遍历序列可有多种 ， 下面仅给出三种 ， 其它可作类似分析。 在无向图 G7中 ， 从顶点 1出发的广度优先搜索遍历序列举三种为： 1, 2, 3, 4, 5, 6, 7, 8 1, 3, 2, 7, 6, 5, 4, 8 1, 2, 3, 5, 4, 7, 6, 8 3 1 2 4 5 7 6 8 8 13 无向图 G 7 用邻接矩阵实现图的广度优先搜索遍历 若从顶点 1 出发 ， 广度优先搜索序列为： 1， 2， 3， 4，5， 6， 7， 8。 若从顶点 3出发 ， 广度优先搜索序列为：3， 1， 6， 7， 2， 8， 4， 5,从其它点出发的广度优先搜索序列可根据同样类似方法分析。 3 1 2 4 5 7 6 8 8 13 无向图 G 7 0111100010000100100001001000001010000010011000010001100100000110 图 8 14 无向图 G 7 的邻接矩阵 用邻接表实现图的广序优先搜索遍历 若从顶点 1出发 ， 广度优先搜索序列为： 1， 2， 3， 4，5， 6， 7， 8， 若从顶点 7出发 ， 广度优先搜索序列为： 7， 3， 8， 1， 6， 4， 5， 2， 从其它顶点出发的广度优先搜索序列可根据同样类似方法分析。 3 1 2 4 5 7 6 8 8 13 无向图 G 7 1 2 3 4 5 6 7 8 2 3 ^ 1 4 1 6 2 8 ^ 2 8 ^ 3 8 ^ 3 8 ^ 4 5 6 7 ^ 7 ^ 5 ^ 图 8 16 G 7 的邻接表 广度优先搜索算法分析 分析前述过程，每个顶点至多进一次队列。 遍历图的过程实质上是通过边或弧找邻接 点的过程、因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之 处仅仅在于对顶点访问的顺序不同。 图遍历的应用 假设图 G采用邻接表存储，设计一个算法，判断无向图 G是否连通。 若连通则返回 1；否则返回 0。 int Connect(ALGraph *G) /*判断无向图 G的连通性 */ { int i,flag=1。 for (i=0。 iGn。 i++) /*visited数组置初值 */ visited[i]=0。 DFS(G,0)。 /*调用 DSF算法 ,从顶点 0开始深度优先遍历 */ for (i=0。 iGn。 i++) if (visited[i]==0) { flag=0。 break。 } return flag。 } 假设图 G采用邻接表存储，设计一个算法，输出图 G中从顶点 u到 v的长度为 l的所有简单路径。 分析：所谓简单路径是指路径上的顶点不重复。 利用回溯的深度优先搜索方法。 从顶点 u开始，进行深度优先搜索，在搜索过程中，需要把当前的搜索线路记录下来。 为此设立一个数组 path保存走过的路径，用 d记录走过的路径长度。 若当前扫描到的结点 u等于 v且路径长度为 l时，表示找到了一条路径，则输出路径 path。 对应的算法如下： void PathAll(ALGraph *G,int u,int v,int l,int path[],int d) /*d是到当前为止已走过的路径长度，调用时初值为 1*/ { int m,i。 ArcNode *p。 visited[u]=1。 d++。 /*路径长度增 1*/ path[d]=u。 /*将当前顶点添加到路径中 */ if (u==v amp。 amp。 d==l) /*输出一条路径 */ { printf( )。 for (i=0。 i=d。 i++) printf(%d ,path[i])。 printf(\n)。 } p=Gadjlist[u].firstarc。 /*p指向 u的第一条弧的弧头结点 */ while (p!=NULL) { m=padjvex。 /*m为 u的邻接顶点 */ if (visited[m]==0) /*若顶点未标记访问 ,则递归访问之 */ PathAll(G,m,v,l,path,d)。 p=pnextarc /*找 u的下一个邻接顶点 */ } visited[u]=0。 /*恢复环境 */ } 图的连通性问题 一 、 无向图的连通分量和生成树 若图是 连通 的或 强连通 的，则从图中 某一个顶点出发可以访问到图中 所有顶点 ； 若图 是非连通 的或 非强连通 图，则需从图中多个顶点 出发搜索访问而每一次从一个新的起始点出发进行搜索，搜索过程中得到的顶点访问序列恰为每个 连通分量 中的 顶点集。 D E A B C F J L M G H I K D E G H I K A B C F J L M 对于 连通图 ， 深度优先搜索遍历算法及广度优先搜索遍历算法中遍历图过程中历经边的集合和顶点集合一起构成 连通图 的 极小连通子图。 它是连通图的一棵 生成树。 生成树： 是一个极小连通子图 ， 它含有图中全部顶点 ， 但只有 n1条边。 由深度优先搜索遍历得到的生成树 ， 称为深度优先生成树 ， 由广度优先搜索遍历得到的生成树 ， 称为 广度优先生成树。 连通图的生成树 1 4 2 5 3 6 8 7 2 7 6 8 3 5 4 1 (a ) 深度优先生成树 (b) 广度优先生成树 图 8 1 9 两种生成树示意图 3 1 2 4 5 7 6 8 8 13 无向图 G 7 例 1 ：画出下图的生成树 DFS生成树 v0 v1 v2 v4 v4 v3邻接表 0 1 2 3 4 ^ 1 3 3 4 ^ 1 4 2 ^ 0 v4 v3 v2 v1 v0 2 3 ^ 1 4 2 ^ 0 v0 v2 v1 v4 v3 BFS生成树 v0 v1 v3 v2 v4 无向连通图 2．生成森林 若一个图 是非连通图 或 非强连通图 ， 但有若干个 连通分量 或若干个 强连通分量 ， 则通过 深度优先 搜索遍历或 广度优先 搜索遍历 ， 不可以 得到生成树 ， 但 可以 得到 生成森林 ， 且若非连通图有 n 个顶点 ， m 个连通分量或强连通分量 ， 则可以遍历得到 m棵生成树 ， 合起来为生成森林 ， 森林中包含 nm条树 边。 生成森林可以利用非连通图的 深度优先搜索遍历 或非连通图的 广度优先搜索遍历算法 得到。 3． 最小生成树 在一般情况下 ， 图中的每条边若给定了 权 ， 这时 ， 我们所关心的不是生成树 ， 而是 生成树中边上权值之和。 若 生成树中每条边上权值之和达到最小 ， 称为 最小生成树。 构造最小生成树的准则 必须只使用该网络中的 边 来构造最小生成树； 必须使用且仅使用 n1条边 来 联结网络中的 n个顶点； 不能使用产生 回路 的边。 欲在 n个城市间建立通信网，则 n个城市应铺 n1条线路；但因为每条线路都会有对应的经济成本，而 n个城市可能有 n(n1)/2 条线路，那么， 如何选择 n–1条线路，使总费用最少。 典型用途： 数学模型： 顶点 ———表示城市，有 n个； 边 ————表示线路，有 n–1条； 边的权值 —表示线路的经济代价； 连通网 ——表示 n个城市间通信网。 问题抽象： n个顶点的生成树很多，需要从中选一棵代价最小 的生成树，即该树 各边的代价之和 最小。 此树便称为最小生成树 MST(Minimum cost Spanning Tree) 显然此连通网是一个 生成树。 求最小生成树的两种方法 普里姆算法和克鲁斯卡尔算法 普里姆 (prim)算法思想 在图中任取一个 顶点 k作为开始点，令 U={k}，W=VU，其中 V为图中所有顶点集，然后找一个 顶点在 U中 ，另 一个顶点在 W中 的 边中最短的一条 ，找到后，将该边作为最小生成树的树边保存起来，并将 该边顶点全部加入 U集合 中，并从 W中删去这些顶点 ，然后重新调整 U中顶点到 W中顶点的距离 , 使之保持 最小 ，再 重复此过程 ，直到 W为空 集止。 例 1 6 5 4 3 2 6 5 1 3 5 6 6 4 2 5 1 3 1 1 6 3 1 4 1 6 4 3 1 4 2 1 1 6 4 3 2 1 4 2 5 1 6 5 4 3 2 1 4 2 5 3 Prim算法构造最小生成树过程 a b c d e g f 例如 :利用 普里姆 算法构造最小生成树 19 5 14 18 27 16 8 21 3 12 7 所得生成树权值和 = 14+8+3+5+16+21 = 67 假设开始顶点就选为顶点 1， 故首先有 U={1}， W={2，3， 4， 5， 6}。