摘要：本文描述了深度优先算法非递归实现的思路，并给出了几个利用深度优先解决的问题的实例代码

关键字：DFS，非递归，深度优先，图论，搜索，经典实例，源码

深度优先搜索算法需要了解深度优先遍历的执行过程，本文中利用一个栈来模拟递归实现中系统设置的工作栈，算法的伪代码描述为：

（1）初始化栈

（2）输出起始节点，并标记为已访问，将该节点压入栈

（3）While（栈不为空）

a.取得栈顶节点Top，注意不要从站内删除;

b.遍历栈顶节点Top的相邻节点adjacentNode，如果该节点adjacentNode未被标记为已

访问，则

输出节点adjacentNode；

标记adjacentNode为已访问；

把adjacentNode压入栈；

c.如果没有满足条件的相邻节点adjacentNode,将栈顶节点Top出栈;

使用情形：

1.深度优先策略常用于连通图的遍历

2.深度优先策略也广泛应用于寻找一条满足某种条件的路径。

算法的时间复杂度为O(n)，其中n为节点个数。

经典实例源码：

1.图的节点遍历(C++,VC6.0/VS2005)=================================================

//////////////////////////////////
//深度优先之节点遍历
//1---5
//|     |
//2---4--6----8
//|          |  
//3------7
// 1 2 3 4 5 6 7 8
//1 0 1 0 0 1 0 0 0
//2 1 0 1 1 0 0 0 0
//3 0 1 0 0 0 0 1 0
//4 0 1 0 0 1 1 0 0
//5 1 0 0 1 0 0 0 0
//6 0 0 0 1 0 0 1 1
//7 0 0 1 0 0 1 0 0
//8 0 0 0 0 0 1 0 0

#include 
#include 
using namespace std;

//节点数
#define M 8

//图的矩阵表示
int matrix[M][M] =
{
    0, 1, 0, 0, 1, 0, 0, 0,
    1, 0, 1, 1, 0, 0, 0, 0,
    0, 1, 0, 0, 0, 0, 1, 0,
    0, 1, 0, 0, 1, 1, 0, 0,
    1, 0, 0, 1, 0, 0, 0, 0,
    0, 0, 0, 1, 0, 0, 1, 1,
    0, 0, 1, 0, 0, 1, 0, 0,
    0, 0, 0, 0, 0, 1, 0, 0

};
//访问标记,初始化为0,
int visited[M + 1];


//graph traverse
void GT_DFS()
{
    visited[1] = 1;
    stack s;
    cout << 1 << " ";
    s.push(1);
    while(!s.empty())
    {
        int top = s.top();
        int i ;
        for(i = 1; i <= M; ++i)
        {
            if(visited[i] == 0 && matrix[top - 1][i - 1 ] == 1)
            {
                visited[i] = 1;
                s.push(i);
                cout << i << " ";

                break;
            }
        }
        if( i == M + 1)
        {
            s.pop();
        }
    }
}


int main()
{
    GT_DFS();
    system("pause");
    return 0;
}

2.迷宫问题（C++,VC6.0/VS2005)=====================================================

////////////////////////////////////////////////
//深度优先搜索之迷宫问题
#include 
#include 
using namespace std;
#define M 10
#define N 10

//迷宫矩阵,1为通道，0为障碍
//入口(1,0),出口(9,9)
int Matrix[M][N]={
    0,1,1,1,0,0,0,0,0,0,
    1,1,0,1,0,1,1,1,1,0,
    0,1,0,1,1,1,0,0,0,0,
    0,0,0,0,0,1,0,0,0,0,
    0,1,1,1,1,1,0,0,0,0,
    0,1,0,0,0,0,0,0,0,0,
    0,1,1,1,0,0,1,1,1,0,
    0,0,1,1,1,1,1,0,1,0,
    0,0,1,1,0,0,0,0,1,0,
    0,0,1,0,0,0,0,0,1,1};
//标记数组,初始化为0
bool visited[M * N + 1] ;

//节点
struct Node
{
    int x;
    int y;
    Node(int i,int j)
    {
        x = i;
        y = j;
    }
};
//////////////////////////////////
/*
   0
   ----------------->y
   |
   |
   |
   |
   |
   V
   x
   */
//右下上左
int x_off[] = {0,1,-1,0};
int y_off[] = {1,0,0,-1};

//输出迷宫
void PrintMatrix()
{
    cout << "入口(1,0),出口(9,9)的迷宫,1为通道,0为障碍:" << endl;
    for(int i = 0; i < M; ++i)
    {
        for(int j = 0; j < N; ++j)
            cout << Matrix[i][j];
        cout << endl;
    }
}

//输出一条路径
//由于入栈路径是正序，要倒过来输出才是从入口到出口的路劲
void PrintPath(stack s)
{
    cout << "一条迷宫路径:" << endl;
    stack t;
    while(!s.empty())
    {
        t.push(s.top());
        s.pop();
    }
    while(!t.empty())
    {
        cout << "(" << t.top().x << "," << t.top().y << ")->";
        t.pop();
    }
    cout << endl;
}

//深度优先搜索一条可能的路径
void MAZE_DFS()
{

    //1.初始化栈
    stack s;
    Node start(1,0);
    s.push(start);
    visited[0] = 1;
    while(!s.empty())
    {
        //2.取得栈顶元素（注意不从栈内删除）
        Node top = s.top();
        //3.遍历栈顶元素的邻节点
        //右节点
        //下节点
        //上节点
        //左节点
        int i;
        for(i = 0; i < 4; ++i)
        {
            int nx = top.x + x_off[i];
            int ny = top.y + y_off[i];
            if(nx >= 0 && nx < N && ny>=0 && ny< M && visited[nx * N + ny] != 1 && Matrix[nx][ny] == 1)
            {
                //4.把满足条件的元素标记为已处理，并压入栈内
                Node newNode(nx,ny);
                visited[nx*N + ny] = 1;
                s.push(newNode);
                //找到出口，终止搜索
                if(nx == 9 && ny == 9)
                {
                    //输出找到的路径
                    PrintPath(s);
                    return;
                }
                break;
            }
        }
        //5.当前节点没有满足条件的邻节点，把当前栈顶元素删除
        if(i == 4)
        {
            s.pop();
        }
    }
}

//测试代码主函数
void main()
{
    PrintMatrix();
    MAZE_DFS();
    system("pause");
}

参考文献:

[1] 深度优先遍历算法的非递归实现jsj.ccut.edu.cn/sjjg/index.php

[2]深度优先遍历演示动画

http://218.65.59.6/xinwen3/news/kj/flash/2004/0426/1301.htm