图的搜索算法.ppt

文档介绍：图的搜索算法
第一页，课件共39页
图的邻接表表示
对图（有向或无向）G=<V, E>（为方便记，假定V={1, 2, …, n}），其邻接表表示是一个由|V|个链表组成数组，对每个u  V，链表Adj[u]称为对应顶点u的邻接表。它包含G中所有与u相邻的顶点。每个邻接表中顶点通常是按任意顺序存放的。
第二页，课件共39页
广度优先搜索
1．问题的理解与描述
给定一个图（有向或无向）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（源顶点）到各节点的距离。
第三页，课件共39页
对一个无向图的BFS操作
第四页，课件共39页
2．算法的伪代码描述
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 d
第五页，课件共39页
3．算法的正确性
引理6-1
从源顶点s到任何顶点v的距离必不超过运行BFS后过此顶点的d属性。
引理6-2
设队列Q={v1, v2, …, vr}。则d[vr]d[v1]+1（即对尾元素的d属性不超过队首元素的d属性加1），且d[v1]d[v2]...d[vr]。
定理6-3
运行BFS后，图G中各顶点v的d属性记录了s到v的距离。
第六页，课件共39页
4．算法的运行时间
第1～4行的循环重复|V|次。另一方面，由于每条边在搜索过程中有且仅有一次被访问，第9～17行两重循环嵌套内的操作被执行|E|次。所以BFS的总运行时间是Θ(V + E)。于是，广度优先搜索运行于G的邻接表示规模的线性时间内。
第七页，课件共39页
深度优先搜索
深度优先搜索（Depth First Search，DFS）所遵循的策略，如同其名称所云，是在图中尽可能“更深”地进行搜索。在深度优先搜索中，对最新发现的顶点v若此顶点尚有未探索过从其出发的边就探索之。当v的所有边都被探索过，搜索“回溯”到从其出发发现顶点v的顶点。此过程继续直至发现所有从源点可达的顶点。若图中还有未发现的顶点，则以其中之一为新的源点重复搜索，直至所有的顶点都被发现。与BFS中源顶点是指定的稍有不同。 DFS搜索轨迹G将形成一片森林—— 深度优先森林
第八页，课件共39页
1．问题的理解与描述
在深度优先搜索过程中对每一个顶点u跟踪两个时间：发现时间d[u]和完成时间f [u]。d[u]记录首次发现（u由白色变成灰色）时刻，f [u]记录完成v的邻接表检测（变成黑色）时刻。
输入：图G=<V, E>。
输出：G的深度优先森林G以及图中各顶点在搜索过程中的发现时间和完成时间。
第九页，课件共39页
2．算法的伪代码描述
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 color[s] = WHITE
8 then color[s] ←