深搜非递归

系统管理员 2022-05-30 05:49 189阅读 0赞

#include <iostream>
    #include <stack>
    using namespace std;
    
    #define MaxNode 20
    #define MAX 2000
    #define StartNode 1
    
    int map[MaxNode+1][MaxNode+1];
    
    void dfs_stack(int start, int n){
        int visited[MaxNode],s_top;
        for(int i = 0;i <= MaxNode; i++){
            visited[i] = 0;
        }
        visited[start] = 1;
        stack <int> s;
        cout<<start<<" ";
        for(int i = 1; i <= n; i++){
            if(map[i][start] == 1 && !visited[i] ){
                visited[i] =  1;
                s.push(i);
            }
        }
        
        while(!s.empty()){
            s_top =  s.top();
            visited[s_top] = 1;
            cout<<s_top<<" ";
            s.pop();
            for(int i = 1; i <= n; i++){
                if(map[i][s_top] == 1 && !visited[i] ){
                    visited[i] = 1;
                    s.push(i);
                }
            }
        }
        
    }
    
    int main(int argc, const char * argv[]) {
        int num_edge,num_node;
        int x,y;
        cout<<"Input number of nodes and edges >"<<endl;
        cin>>num_node>>num_edge;
        for(int i =0;i<num_node;i++){
            for(int j=0;j<num_node;j++){
                map[i][j] = 0;
            }
        }
        for(int i = 1; i <= num_edge; i++){
            cin>>x>>y;
            map[x][y] = map[y][x] = 1;
        }
        
        dfs_stack(StartNode, num_node);
    
        return 0;
    }

栈实现的基本思路是将一个节点所有未被访问的“邻居”（即“一层邻居节点”）踹入栈中“待用”，然后围绕顶部节点猛攻，每个节点被访问后被踹出。读者可以自己画图分析一下，难度并不大。 代码写的比较随意，仅供参考。~

发表评论取消回复

表情：

评论列表（有 0 条评论，189人围观）

还没有评论，来说两句吧...

相关阅读

相关 BTree非递归

preorder void PreOrder(BTNode b) { BTNode p = b; SqStack st; Ini

小鱼儿/ 2023年08月17日 15:15/ 0 赞/ 126 阅读

相关二分查找(递归和非递归)

二分查找 (非递归) 1. 二分查找法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找 2. 二分查找法的运行时间为对数时间 O(㏒₂n)

素颜马尾好姑娘i/ 2023年07月24日 11:45/ 0 赞/ 59 阅读

相关深拷贝（递归）

function clone(obj){ if(typeof obj==="Object"&&typeof obj!=="null"){ v

男娘i/ 2022年12月25日 12:53/ 0 赞/ 33 阅读

相关二分查找（递归+非递归）

文章目录二分查找递归实现非递归实现附加问题：安全防溢出的两整数平均值算法相关一些题目题一：无目标值，返回插入序号

悠悠/ 2022年12月07日 11:56/ 0 赞/ 220 阅读

相关快速排序递归与非递归

递归法快排的思想设当前需要排序的数组为int A\[bt...ed\] 分解：在A\[\]中任选一个记录作为基准（pivot

素颜马尾好姑娘i/ 2022年09月18日 01:59/ 0 赞/ 222 阅读

相关二叉树递归非递归

include <iostream> include <string.h> include <stack> include <windows.

ゞ浴缸里的玫瑰/ 2022年07月14日 07:43/ 0 赞/ 217 阅读

相关深搜（非递归）实现获取两点之间的路径

用栈实现求两点之间的所有路径： // dfs.cpp : Defines the entry point for the console application.

曾经终败给现在/ 2022年05月30日 12:08/ 0 赞/ 168 阅读

相关深搜（非递归）实现获取两点之间的路径（起点和终点不重合）

// dfs.cpp : Defines the entry point for the console application. // in

心已赠人/ 2022年05月30日 11:59/ 0 赞/ 169 阅读

相关深搜非递归

include <iostream> include <stack> using namespace std; define MaxN

系统管理员/ 2022年05月30日 05:49/ 0 赞/ 190 阅读

相关归并排序（递归和非递归）

学习之后，自己练习手写一下排序算法，加深印象原理：假设初始序列含有n个记录，则可以看做是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的子序

水深无声/ 2022年05月28日 01:44/ 0 赞/ 250 阅读