关于深度优先搜索 dfs

时间：2010-12-06 来源：niuniu2006t

关于深度优先搜索，我想大家都很熟悉了，他是尽可能深的挖掘一个图，当无法继拓展时，就向上回溯一步，然后找一个可以挖掘的点，然后继续调用此过程。如果让你写他的递归过程，我想大家很容易写出来。关于非递归过程，也就是用堆栈来实现，如果想想的话，还是比较容易实现的。但是如果让你用非递归，非堆栈来实现图的深度优先搜索呢？其实好好想想，也是能实现的 : ) 在深度优先里面，最关键的是在进行下次递归的拓展时，需要保存当前的状态，即当前的节点以及其访问的子节点的位置。当我们用递归来写时，编译器自动帮我们实现了。如果我们用自己定义的堆栈来写时，堆栈做的其实就是把当前正在访问的节点的父亲节点以及父亲节点对子节点的访问情况记到栈顶。这样当我们访问的节点以及其深度优先访问树的拓展完毕后，只要根据栈顶的信息，就可以确定下一个需要访问的节点。可以发现，其实堆栈就是保存当前访问节点的父亲节点。如果我们用一个额外的数据结构来存储这个信息，其实堆栈也可以不用的。首先我先把这个逻辑的循环不变式写出来： 0.初始化,要访问的第一个节点i,x=i,pai(x)=-1; 1.访问当前节点x 2.查找一个可可以拓展的相邻节点 3.1如果在2中能找到节点y,那么x=y,pai(y)=x goto 1. 3.2如果在2中不能找到合适的节点，那么x=pai(x) //即x等于其父亲节点，进行回溯 4.1 如果x==-1 goto END 4.1 goto 1 . END
下面是代码,我输入的图是一个连通图，故只dfs一次，就能便利所有节点了。

#include <iostream>
#include <vector>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

const int LEN = 100;
vector< int > graph[LEN];
bool ckd[LEN]; //check for visited

int pai[LEN]; //parent of node i

int cnt[LEN]; //the next son to visit

void dfs(int i)
{
  int nxt = i;
  while(1)
  {
    bool find = false;
    if(!ckd[nxt])
    {
      cout<<"visit "<<nxt<<endl;
      ckd[nxt]=true;
    }
    while(cnt[nxt]<graph[nxt].size())
    {
      if(!ckd[graph[nxt][cnt[nxt]]])
      {
    int    temnxt = graph[nxt][cnt[nxt]];
    pai[temnxt] = nxt;
    cnt[nxt]++;
    nxt=temnxt;
    find = true;
    break;
      }
      cnt[nxt]++;
    }
    if(!find)
    {
      cout<<"node "<<nxt<<" can't find nxt and now return to pai ";
      nxt = pai[nxt];
      cout<<nxt<<endl;
      if(nxt==-1)
    break;
      assert(ckd[nxt]);
    }

  }
}

int main()
{
  freopen("in.txt","r",stdin);
  memset(pai,-1,sizeof(pai));
  memset(ckd,0,sizeof(ckd));
  memset(cnt,0,sizeof(cnt));

  int n,s;
  cin>>n>>s;
  for(int i=0;i<n;++i)
  {
    int node;
    while(cin>>node)
    {
      if(node==-1)break;
      graph[i].push_back(node);
    }
  }

  dfs(s);
  return 0;
}

顺便附上测试数据一组 9 0 1 2 -1 0 2 3 -1 0 1 7 -1 1 8 -1 1 5 6 -1 4 -1 4 7 -1 2 6 -1 3 -1