第 6 章 图的搜索算法.ppt

第 6 章图的搜索算法图的邻接表表示?对图(有向或无向) G =<V , E>(为方便记,假定V ={1, 2, …, n}), 其邻接表表示是一个由|V| 个链表组成数组,对每个 u ?V,链表 Adj [u]称为对应顶点 u的邻接表。它包含 G中所有与 u相邻的顶点。每个邻接表中顶点通常是按任意顺序存放的。 广度优先搜索??给定一个图(有向或无向) G = < V, E >和其中的一个源顶点 s,广度优先搜索系统地探索 G的边以“发现”从s出发每一个可达的顶点:发现从 s出发距离为 k +1的顶点之前先发现距离为 k的顶点。搜索所经路径中的顶点,按先后顺序构成“父子关系”:先发现的顶点 u,并由 u出发发现与其相邻的顶点 v,则称 u为v的父亲。由于每个顶点只有最多一个顶点作为它的父亲,所以搜索路径必构成一棵根树(树根为起始顶点 s)G ?。我们把这棵树称为 G 的广度优先树。与此同时,我们还计算出了从 s到这些可达顶点的距离(最少的边数即“最短路径”)。这样,图的广度搜索问题形式化表述如下。?输入:图 G =<V , E>,源顶点 s?V。?输出:G的广度优先树 G ?以及树中从树根 s(源顶点)到各节点的距离。对一个无向图的 BFS 操作 ? BFS( G,s )? 1 for 每个顶点 u?V[G ] - { s}? 2 do color [u]← WHITE ? 3 d[u]←?? 4 ?[u ] ← NIL ? 5 color [s ] ← GRAY ? 6 d[s]←0? 7 Q←?? 8 ENQUEUE( Q,s )? 9 while Q≠?? 10 do u← DEQUEUE( Q)? 11 for each v? Adj [u]? 12 do if color [v ] = WHITE ? 13 then color [v]← GRAY ? 14?[v ] ←u ? 15 d[v]←d[u ] + 1 ? 16 ENQUEUE( Q,v ) ? 17 color [u]← BLACK ? 18 return ? and ?引理 6-1 ?从源顶点 s到任何顶点 v的距离必不超过运行 BFS 后过此顶点的 d属性。?引理 6-2 ?设队列 Q ={v 1 , v 2 , …, v r}。则 d[v r]?d[v 1 ]+1 (即对尾元素的 d属性不超过队首元素的 d属性加 1), 且d[v 1]?d[v 2]?...?d[v r]。?定理 6-3 ?运行 BFS 后,图 G中各顶点 v的d属性记录了 s到v 的距离。 ?第1~4行的循环重复|V|次。另一方面,由于每条边在搜索过程中有且仅有一次被访问,第 9~ 17行两重循环嵌套内的操作被执行|E|次。所以 BFS 的总运行时间是Θ( V + E)。于是,广度优先搜索运行于 G的邻接表示规模的线性时间内。 深度优先搜索?深度优先搜索( Depth First Search , DFS )所遵循的策略,如同其名称所云,是在图中尽可能“更深”地进行搜索。在深度优先搜索中,对最新发现的顶点 v若此顶点尚有未探索过从其出发的边就探索之。当 v的所有边都被探索过,搜索“回溯”到从其出发发现顶点 v的顶点。此过程继续直至发现所有从源点可达的顶点。若图中还有未发现的顶点, 则以其中之一为新的源点重复搜索,直至所有的顶点都被发现。与 BFS 中源顶点是指定的稍有不同。 DFS 搜索轨迹 G ?将形成一片森林——深度优先森林 ?在深度优先搜索过程中对每一个顶点 u跟踪两个时间:发现时间 d[u]和完成时间 f [u]。 d[u]记录首次发现( u由白色变成灰色)时刻, f [u]记录完成 v的邻接表检测(变成黑色)时刻。?输入:图 G =<V , E>。?输出:G的深度优先森林 G ?以及图中各顶点在搜索过程中的发现时间和完成时间。 ? DFS( G)? 1 for each vertex u?V[G]? 2 do color [u]← WHITE ? 3 ?[u ] ← NIL ? 4 time ← 0 ? 5 S←?? 6 for each vertex s?V[G]? 7 do if col