深度优先搜索(DFS)基础

       深度优先搜索(Deep First Search)主要用在回溯，搜索剪枝等类的问题上。

DFS的基本算法思想是：从图中一顶点vi出发，访问它，并进行标记，然后依次搜索vi的每个邻接点vj；若vj没被访问过，则对vj进行访问标记，然后，依次搜索vj的每个邻接点；若vj的邻接点没被访问过，则访问vj 的邻接点，并进行标记……直到图中和vi有通路的所有顶点都被访问。

       二叉树的先序遍历是DFS的一种小范围情况:

实线表调用，虚线表返回(回溯)。得到ABDEGCF.

void Preorder(BiTree root)
         {
           if (root==NULL)  return; 
           else
           { 
           访问根结点；
             Preorder(root->Lchild);
             Preorder(root->Rchild);
           }
        } 

    对于图的DFS，也是依据上述思想……

     DFS(从V1开始)得到

void DFS(int start)
{ 
 node *p=G[start].link;
 visited[start]=1;    //标记节点是否被访问
 while(p!=NULL)
 {
  if(!visited[p->num]);
   DFS(p->num);  //对vi的每个邻接点递归进行DFS
  p=p->next;
 }
}

评论