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

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

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

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

最后，咱們再來看深度優(yōu)先搜索的遞歸實現(xiàn)與非遞歸實現(xiàn)
1、DFS 遞歸實現(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當為v的鄰接點。
              if(v1->marked==0)
                     dfsR(inGraph,v1);
}

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

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

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

將算法通過精簡過的C源程序的方式描述如下:

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

 do
 {
  flag2=0;
  //flag2是一個重要的標志變量，用以、說明當前結(jié)點的所有未訪問結(jié)點的個數(shù),兩個以上的用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);    //鄰接點v1
  while(v1!=NULL) //訪問當前結(jié)點的所有鄰接點 
  {
   if(v1->marked==0) //..

   {    
    if(flag2==0)   //當前結(jié)點的鄰接點有0個未訪問

    {
     //首先，訪問最左結(jié)點
     visit(v1);
     v1->marked=1;    //訪問完成
     flag2=1;       //

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

    {
     //新建一個隊列，申請空間，并加入第一個結(jié)點      
     flag2=2;
    }
    else if(flag2==2)//當前結(jié)點的鄰接點有2個未被訪問

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

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