当前位置:编程学习 > C/C++ >>

经典算法研究系列:四、教你通透彻底理解:BFS和DFS优先搜索算法

4、教你通透彻底理解:BFS和DFS优先搜索算法

 

 作者:July  二零一一年一月一日

---------------------------------

本人参考:算法导论
本人声明:个人原创,转载请注明出处。

ok,开始。

翻遍网上,关于此类BFS和DFS算法的文章,很多。但,都说不出个所以然来。
读完此文,我想,
你对图的广度优先搜索和深度优先搜索定会有个通通透透,彻彻底底的认识。

---------------------

咱们由BFS开始:
首先,看下算法导论一书关于 此BFS 广度优先搜索算法的概述。
算法导论第二版,中译本,第324页。
广度优先搜索(BFS)
在Prime最小生成树算法,和Dijkstra单源最短路径算法中,都采用了与BFS 算法类似的思想。

//u 为 v 的先辈或父母。
BFS(G, s)
 1  for each vertex u ∈ V [G] - {s}
 2       do color[u] ← WHITE
 3          d[u] ← ∞
 4          π[u] ← NIL
  //除了源顶点s之外,第1-4行置每个顶点为白色,置每个顶点u的d[u]为无穷大,
  //置每个顶点的父母为NIL。
 5  color[s] ← GRAY
  //第5行,将源顶点s置为灰色,这是因为在过程开始时,源顶点已被发现。
 6  d[s] ← 0       //将d[s]初始化为0。
 7  π[s] ← NIL     //将源顶点的父顶点置为NIL。
 8  Q ← Ø
 9  ENQUEUE(Q, s)                  //入队
  //第8、9行,初始化队列Q,使其仅含源顶点s。
10  while Q ≠ Ø
11      do u ← DEQUEUE(Q)    //出队
  //第11行,确定队列头部Q头部的灰色顶点u,并将其从Q中去掉。
12         for each v ∈ Adj[u]        //for循环考察u的邻接表中的每个顶点v
13             do if color[v] = WHITE
14                   then color[v] ← GRAY     //置为灰色
15                        d[v] ← d[u] + 1     //距离被置为d[u]+1
16                        π[v] ← u            //u记为该顶点的父母
17                        ENQUEUE(Q, v)        //插入队列中
18         color[u] ← BLACK      //u 置为黑色

 \

由下图及链接的演示过程,清晰在目,也就不用多说了:

 

\

广度优先遍历演示地址:

html">http://sjjg.js.zwu.edu.cn/SFXX/sf1/gdyxbl.html


-----------------------------------------------------------------------------------------------------------------
ok,不再赘述。接下来,具体讲解深度优先搜索算法。
深度优先探索算法 DFS
//u 为 v 的先辈或父母。
DFS(G)
1  for each vertex u ∈ V [G]
2       do color[u] ← WHITE
3          π[u] ← NIL
//第1-3行,把所有顶点置为白色,所有π 域被初始化为NIL。
4  time ← 0       //复位时间计数器
5  for each vertex u ∈ V [G]
6       do if color[u] = WHITE
7             then DFS-VISIT(u)  //调用DFS-VISIT访问u,u成为深度优先森林中一棵新的树
    //第5-7行,依次检索V中的顶点,发现白色顶点时,调用DFS-VISIT访问该顶点。
    //每个顶点u 都对应于一个发现时刻d[u]和一个完成时刻f[u]。
DFS-VISIT(u)
1  color[u] ← GRAY            //u 开始时被发现,置为白色
2  time ← time +1             //time 递增
3  d[u] <-time                   //记录u被发现的时间
4  for each v ∈ Adj[u]   //检查并访问 u 的每一个邻接点 v
5       do if color[v] = WHITE            //如果v 为白色,则递归访问v。
6             then π[v] ← u                   //置u为 v的先辈
7                         DFS-VISIT(v)        //递归深度,访问邻结点v
8  color[u] <-BLACK         //u 置为黑色,表示u及其邻接点都已访问完成
9  f [u] ▹ time ← time +1  //访问完成时间记录在f[u]中。
//完
第1-3行,5-7行循环占用时间为O(V),此不包括调用DFS-VISIT的时间。
    对于每个顶点v(-V,过程DFS-VISIT仅被调用依次,因为只有对白色顶点才会调用此过程。
第4-7行,执行时间为O(E)。
因此,总的执行时间为O(V+E)。
 
下面的链接,给出了深度优先搜索的演示系统:

\

 

\

 


图的深度优先遍历演示系统:

http://sjjg.js.zwu.edu.cn/SFXX/sf1/sdyxbl.html

 

===============

最后,咱们再来看深度优先搜索的递归实现与非递归实现
1、DFS 递归实现:
void dftR(PGraphMatrix inGraph)
{
       PVexType v;
       assertF(inGraph!=NULL,"in dftR, pass in inGraph is null ");
       printf(" ===start of dft recursive version=== ");
       for(v=firstVertex(inGraph);v!=NULL;v=nextVertex(inGraph,v))
              if(v->marked==0)
                     dfsR(inGraph,v);
       printf(" ===end of   dft recursive version=== ");
}

void dfsR(PGraphMatrix inGraph,PVexType inV)
{
       PVexType v1;
       assertF(inGraph!=NULL,"in dfsR,inGraph is null ");
       assertF(inV!=NULL,"in dfsR,inV is null ");
       inV->marked=1;
       visit(inV);
       for(v1=firstAdjacent(inGraph,inV);v1!=NULL;v1=nextAdjacent(inGraph,inV,v1))
       //v1当为v的邻接点。
   

补充:软件开发 , C语言 ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,