• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    迪恩网络公众号

深度优先搜索算法之非递归实现及实例源码(原创)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

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

关键字: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


鲜花

握手

雷人

路过

鸡蛋
专题导读
上一篇:
二叉搜索树(BST)的实现(C语言)(原创)发布时间:2022-05-14
下一篇:
广度优先搜索算法思路及实例(原创)发布时间:2022-05-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap