經(jīng)典算法研究系列；BFS和DFS優(yōu)先搜索算法(2)

圖的深度優(yōu)先遍歷演示系統(tǒng)：

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

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

最后，咱們?cè)賮?lái)看深度優(yōu)先搜索的遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn)
1、DFS 遞歸實(shí)現(xiàn)：
void dftR(PGraphMatrix inGraph)
{
       PVexType v; 
       assertF(inGraph!=NULL,"in dftR, pass in inGraph is null/n");
       printf("/n===start of dft recursive version===/n");
       for(v=firstVertex(inGraph);v!=NULL;v=nextVertex(inGraph,v))
              if(v->marked==0)
                     dfsR(inGraph,v);
       printf("/n===end of   dft recursive version===/n");
}

void dfsR(PGraphMatrix inGraph,PVexType inV)
{
       PVexType v1;
       assertF(inGraph!=NULL,"in dfsR,inGraph is null/n");
       assertF(inV!=NULL,"in dfsR,inV is null/n");
       inV->marked=1;
       visit(inV);
       for(v1=firstAdjacent(inGraph,inV);v1!=NULL;v1=nextAdjacent(inGraph,inV,v1))
       //v1當(dāng)為v的鄰接點(diǎn)。
              if(v1->marked==0)
                     dfsR(inGraph,v1);
}

2、DFS 非遞歸實(shí)現(xiàn)
非遞歸版本---借助結(jié)點(diǎn)類(lèi)型為隊(duì)列的棧實(shí)現(xiàn)
   聯(lián)系樹(shù)的前序遍歷的非遞歸實(shí)現(xiàn)：
   可知，其中無(wú)非是分成“探左”和“訪(fǎng)右”兩大塊訪(fǎng)右需借助棧中彈出的結(jié)點(diǎn)進(jìn)行.
   在圖的深度優(yōu)先搜索中，同樣可分成“深度探索”和“回訪(fǎng)上層未訪(fǎng)結(jié)點(diǎn)”兩塊:
    1、圖的深度探索這樣一個(gè)過(guò)程和樹(shù)的“探左”完全一致,
只要對(duì)已訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)作一個(gè)判定即可。
    2、而圖的回訪(fǎng)上層未訪(fǎng)結(jié)點(diǎn)和樹(shù)的前序遍歷中的“訪(fǎng)右”也是一致的.
但是，對(duì)于樹(shù)而言，是提供rightSibling這樣的操作的，因而訪(fǎng)右相當(dāng)好實(shí)現(xiàn)。

在這里，若要實(shí)現(xiàn)相應(yīng)的功能，考慮將每一個(gè)當(dāng)前結(jié)點(diǎn)的下層結(jié)點(diǎn)中，如果有m個(gè)未訪(fǎng)問(wèn)結(jié)點(diǎn),
則最左的一個(gè)需要訪(fǎng)問(wèn)，而將剩余的m-1個(gè)結(jié)點(diǎn)按從左到右的順序推入一個(gè)隊(duì)列中。
并將這個(gè)隊(duì)列壓入一個(gè)堆棧中。

   這樣，當(dāng)當(dāng)前的結(jié)點(diǎn)的鄰接點(diǎn)均已訪(fǎng)問(wèn)或無(wú)鄰接點(diǎn)需要回訪(fǎng)時(shí)，
則從棧頂?shù)年?duì)列結(jié)點(diǎn)中彈出隊(duì)列元素，將隊(duì)列中的結(jié)點(diǎn)元素依次出隊(duì),
若已訪(fǎng)問(wèn)，則繼續(xù)出隊(duì)(當(dāng)當(dāng)前隊(duì)列結(jié)點(diǎn)已空時(shí)，則繼續(xù)出棧，彈出下一個(gè)棧頂?shù)年?duì)列)，
直至遇到有未訪(fǎng)問(wèn)結(jié)點(diǎn)(訪(fǎng)問(wèn)并置當(dāng)前點(diǎn)為該點(diǎn))或直到棧為空（則當(dāng)前的深度優(yōu)先搜索樹(shù)停止搜索）。

將算法通過(guò)精簡(jiǎn)過(guò)的C源程序的方式描述如下:

//dfsUR:功能從一個(gè)樹(shù)的某個(gè)結(jié)點(diǎn)inV發(fā)，以深度優(yōu)先的原則訪(fǎng)問(wèn)所有與它相鄰的結(jié)點(diǎn)
void dfsUR(PGraphMatrix inGraph,PVexType inV)
{
 PSingleRearSeqQueue tmpQ;  //定義臨時(shí)隊(duì)列，用以接受棧頂隊(duì)列及壓棧時(shí)使用
 PSeqStack testStack;       //存放當(dāng)前層中的m-1個(gè)未訪(fǎng)問(wèn)結(jié)點(diǎn)構(gòu)成隊(duì)列的堆棧.
 //一些變量聲明,初始化動(dòng)作
 //訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)
 inV->marked=1;    //當(dāng)marked值為1時(shí)將不必再訪(fǎng)問(wèn)。
 visit(inV);

 do
 {
  flag2=0;
  //flag2是一個(gè)重要的標(biāo)志變量，用以、說(shuō)明當(dāng)前結(jié)點(diǎn)的所有未訪(fǎng)問(wèn)結(jié)點(diǎn)的個(gè)數(shù),兩個(gè)以上的用2代表
  //flag2:0:current node has no adjacent which has not been visited.
  //1:current node has only one adjacent node which has not been visited.
  //2:current node has more than one adjacent node which have not been visited.
  
  v1=firstAdjacent(inGraph,inV);    //鄰接點(diǎn)v1
  while(v1!=NULL) //訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)的所有鄰接點(diǎn) 
  {
   if(v1->marked==0) //..

   {    
    if(flag2==0)   //當(dāng)前結(jié)點(diǎn)的鄰接點(diǎn)有0個(gè)未訪(fǎng)問(wèn)

    {
     //首先，訪(fǎng)問(wèn)最左結(jié)點(diǎn)
     visit(v1);
     v1->marked=1;    //訪(fǎng)問(wèn)完成
     flag2=1;       //

     //記錄最左兒子
     lChildV=v1;   
     //save the current node's first unvisited(has been visited at this time)adjacent node
    }      
    else if(flag2==1)   //當(dāng)前結(jié)點(diǎn)的鄰接點(diǎn)有1個(gè)未訪(fǎng)問(wèn)

    {
     //新建一個(gè)隊(duì)列，申請(qǐng)空間，并加入第一個(gè)結(jié)點(diǎn)      
     flag2=2;
    }
    else if(flag2==2)//當(dāng)前結(jié)點(diǎn)的鄰接點(diǎn)有2個(gè)未被訪(fǎng)問(wèn)

    {
     enQueue(tmpQ,v1);
    }
   }
   v1=nextAdjacent(inGraph,inV,v1);
  }

  if(flag2==2)//push adjacent  nodes which are not visited.
  {            
   //將存有當(dāng)前結(jié)點(diǎn)的m-1個(gè)未訪(fǎng)問(wèn)鄰接點(diǎn)的隊(duì)列壓棧
   seqPush(testStack,tmpQ);
   inV=lChildV;
  }
  else if(flag2==1)//only has one adjacent which has been visited. 
  {           
   //只有一個(gè)最左兒子，則置當(dāng)前點(diǎn)為最左兒子
   inV=lChildV;
  }
  else if(flag2==0)
   //has no adjacent nodes or all adjacent nodes has been visited
  {    
  //當(dāng)當(dāng)前的結(jié)點(diǎn)的鄰接點(diǎn)均已訪(fǎng)問(wèn)或無(wú)鄰接點(diǎn)需要回訪(fǎng)時(shí)，則從棧頂?shù)年?duì)列結(jié)點(diǎn)中彈出隊(duì)列元素，
  //將隊(duì)列中的結(jié)點(diǎn)元素依次出隊(duì),若已訪(fǎng)問(wèn)，則繼續(xù)出隊(duì)(當(dāng)當(dāng)前隊(duì)列結(jié)點(diǎn)已空時(shí)，
  //則繼續(xù)出棧，彈出下一個(gè)棧頂?shù)年?duì)列)，直至遇到有未訪(fǎng)問(wèn)結(jié)點(diǎn)(訪(fǎng)問(wèn)并置當(dāng)前點(diǎn)為該點(diǎn))或直到棧為空。
   flag=0;
   while(!isNullSeqStack(testStack)&&!flag)
   {    
    v1=frontQueueInSt(testStack);  //返回棧頂結(jié)點(diǎn)的隊(duì)列中的隊(duì)首元素
    deQueueInSt(testStack);     //將棧頂結(jié)點(diǎn)的隊(duì)列中的隊(duì)首元素彈出
    if(v1->marked==0)
    {      
     visit(v1);
     v1->marked=1;
     inV=v1;
     flag=1;                                 
    }
   }
  }                                
 }while(!isNullSeqStack(testStack));//the algorithm ends when the stack is null
 
}