经典算法研究系列；BFS和DFS优先搜索算法(2)

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

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/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 非递归实现
非递归版本---借助结点类型为队列的栈实现
   联系树的前序遍历的非递归实现：
   可知，其中无非是分成“探左”和“访右”两大块访右需借助栈中弹出的结点进行.
   在图的深度优先搜索中，同样可分成“深度探索”和“回访上层未访结点”两块:
    1、图的深度探索这样一个过程和树的“探左”完全一致,
只要对已访问过的结点作一个判定即可。
    2、而图的回访上层未访结点和树的前序遍历中的“访右”也是一致的.
但是，对于树而言，是提供rightSibling这样的操作的，因而访右相当好实现。

在这里，若要实现相应的功能，考虑将每一个当前结点的下层结点中，如果有m个未访问结点,
则最左的一个需要访问，而将剩余的m-1个结点按从左到右的顺序推入一个队列中。
并将这个队列压入一个堆栈中。

   这样，当当前的结点的邻接点均已访问或无邻接点需要回访时，
则从栈顶的队列结点中弹出队列元素，将队列中的结点元素依次出队,
若已访问，则继续出队(当当前队列结点已空时，则继续出栈，弹出下一个栈顶的队列)，
直至遇到有未访问结点(访问并置当前点为该点)或直到栈为空（则当前的深度优先搜索树停止搜索）。

将算法通过精简过的C源程序的方式描述如下:

//dfsUR:功能从一个树的某个结点inV发，以深度优先的原则访问所有与它相邻的结点
void dfsUR(PGraphMatrix inGraph,PVexType inV)
{
 PSingleRearSeqQueue tmpQ;  //定义临时队列，用以接受栈顶队列及压栈时使用
 PSeqStack testStack;       //存放当前层中的m-1个未访问结点构成队列的堆栈.
 //一些变量声明,初始化动作
 //访问当前结点
 inV->marked=1;    //当marked值为1时将不必再访问。
 visit(inV);

 do
 {
  flag2=0;
  //flag2是一个重要的标志变量，用以、说明当前结点的所有未访问结点的个数,两个以上的用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) //访问当前结点的所有邻接点 
  {
   if(v1->marked==0) //..

   {    
    if(flag2==0)   //当前结点的邻接点有0个未访问

    {
     //首先，访问最左结点
     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)   //当前结点的邻接点有1个未访问

    {
     //新建一个队列，申请空间，并加入第一个结点      
     flag2=2;
    }
    else if(flag2==2)//当前结点的邻接点有2个未被访问

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

  if(flag2==2)//push adjacent  nodes which are not visited.
  {            
   //将存有当前结点的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
  {    
  //当当前的结点的邻接点均已访问或无邻接点需要回访时，则从栈顶的队列结点中弹出队列元素，
  //将队列中的结点元素依次出队,若已访问，则继续出队(当当前队列结点已空时，
  //则继续出栈，弹出下一个栈顶的队列)，直至遇到有未访问结点(访问并置当前点为该点)或直到栈为空。
   flag=0;
   while(!isNullSeqStack(testStack)&&!flag)
   {    
    v1=frontQueueInSt(testStack);  //返回栈顶结点的队列中的队首元素
    deQueueInSt(testStack);     //将栈顶结点的队列中的队首元素弹出
    if(v1->marked==0)
    {      
     visit(v1);
     v1->marked=1;
     inV=v1;
     flag=1;                                 
    }
   }
  }                                
 }while(!isNullSeqStack(testStack));//the algorithm ends when the stack is null
 
}