dfs非递归java（DFS非递归算法）

发布时间：2022-11-15

本文目录一览：

  1. DFS 递归为什么比非递归要快？？？
  2. 设计一个基于深度优先遍历的算法，判断一个给定的有向图是否包含回路。
  3. 如何将回溯法dfs改写为非递归的
  4. 数据结构图的遍历 1)先任意创建一个图； 2)图的DFS,BFS的递归和非递归算法的实现 3)要求用有向图和无向图

DFS 递归为什么比非递归要快？？？

非递归肯定要快一些，递归的话需要不断的调用自己的函数原型，每调用一次都需要增长栈来存储变量，而且返回前还需要将当前结果写入在返回地址中，对内存使用效率极低。

设计一个基于深度优先遍历的算法，判断一个给定的有向图是否包含回路。

你好，关于DFS判断有向图是否存在回路的问题，我本人编写的考研资料中有相关的原创总结，希望对你有帮助，转载还请注明原创出处：《大连理工大学软件学院887专业课（2021版）》。如有问题可以加我QQ601964408交流。

法一：利用递归方式

在DFS对图进行遍历时，将遍历过的顶点放入栈中，如果新遍历的顶点已经存在于递归栈中，则说明存在一个反向边，即存在一个环。此时栈中结点刚好是环路中的所有结点！ 注意该方法没办法用DFS的非递归方法实现，因为非递归方法中，利用出栈的结点获取下一个邻接点入栈，和递归方式不同的地方在于，即使图中有环，非递归方法中的栈也无法存储环上的结点。

代码实现如下：

void HasCycle ( Graph G ) {
    bool visited [MAX_VERTEX_NUM] ; //访问标记数组
    bool recursionStack [MAX_VERTEX_NUM] ; //标记该点是否在栈中
    for ( i=0 ; i < G.vexnum ; i++) {
        //mark all the vertices as not visited and not part of recursion stack
        //标记所有结点均未访问以及不在栈中
        visited [i] = FALSE ;
        recursionStack [i] = FALSE ;
    }
    //call the recursive helper function to detect cycle in different DFS trees
    //调用辅助递归函数以检测不同DFS树种的环路
    for ( int i =0 ; i < G.vexnum ; i++ ) //每次检测一个连通图
        if ( CheckCyclic ( G , i , visited , recursionStack ) ) ;
    return true ; //存在回路
    return false ; //不存在回路
}
bool CheckCyclic ( Graph G , int v , bool [ ] visited , bool [ ] recursionStack ) {
    if ( visited [v] == FALSE) {
        //mark the current nodes as visited and part of recursion stack
        //将当前结点的标记数组和递归栈标记，置为已访问
        visited [v] = TRUE ;
        recursionStack [v] = TRUE ;
        //recursion for all the vertices adjacent to this vertex
        //递归该顶点附近的所有顶点
        for ( Edge e = G.FirstEdge(v) ; G.IsEdge(e) ; e=G.NextEdge(e) ) {
            //判断下一结点未被访问，进入递归函数判断是否有环
            if ( visited [G.ToVertex(e) ] == FALSE)
                CheckCyclic ( G , G.ToVertex(e) , visited , recursionStack) )
                return TRUE ;
            //当下一结点已经访问过，并且已经在栈中，判断有环
            else if ( recursionStack (G.ToVertex(e) ) == TRUE )
                return TRUE ;
        }//end_for
    }//end_if
    //remove the vertex from recursion stack
    //从递归栈种移除该结点
    recursionStack [v] = FALSE ;
    return false ; //判断无环
}

法二：与法一非常相似

本方法与法一非常相似，方法一中存在三种情况，还未入栈时表示未被访问过的点；在栈中时表示已经被访问过但是还没有递归结束；从栈中出栈时表示递归结束，即后代也全部被访问过了。上述三种情况分别用 -1，0，1三种状态来标记点。 针对上述思路，假设正在处理点v，那么v的状态是0，其余正在处理的结点的状态也是0，如果从状态0的结点遍历到状态为0的结点，那么就存在环。此时所有状态为0的结点构成了一个环！发现存在环时遍历输出state数组即可，不过该方法输出时不是按照环路的顺序输出；如果需要顺序输出环路，可增加一个cycle数组，每次记录环路的起点位置i。用cycle[i]记录结点i的下一个结点编号。利用递归的方式输出cycle数组即可得到回路顺序。

代码实现：

bool Found = FALSE ; //标记是否发现环路
void HasCycle ( Graph G ) {
    int state [MAX_VERTEX_NUM] ; //结点状态标识数组
    for ( i=0 ; i < G.vexnum ; i++) {
        state [i] = -1 ;
    }
    for ( int i =0 ; i < G.vexnum ; i++ ) { //每次检测一个连通图
        CheckCyclic ( G , i , state )；
        if ( Found == TRUE ) ; //存在回路
            return true ;
    }
    return false ; //不存在回路
}
void CheckCyclic ( Graph G , int v , int [ ] state ) {
    if ( state [v] == -1) { //如果未访问过
        state [v] = 0 ; //改变该点的状态
        for ( Edge e = G.FirstEdge(v) ; G.IsEdge(e) ; e=G.NextEdge(e) ) {
            if ( state [ G.ToVertex(e) ] == -1 )
                CheckCyclic ( G , G.ToVertex(e) , state )
            else if ( state [ G.ToVertex(e) ] == 0 ) //该图有环
                Found = TRUE ;
        }//end_for
    }//end_if
    state [v] = 1 ; //该点递归结束，即后代也访问完
}

如何将回溯法dfs改写为非递归的

我的印象中貌似回溯法本身就是基于dfs的算法，俗称爆搜？ 可以写人工栈，但是如果在竞赛中的话写人工栈意义不大，Linux下本身就有80W左右的栈空间，而且人工栈不见得就比系统的快。 人工栈的原理非常简单，就是开若干个数组，每个数组对应开一个指针t，把原来dfs中每一层的信息都记录到数组里，dfs改成循环，如while (t!=0) ，要进入一层时t++，当退出一层时t--即可。

数据结构图的遍历 1)先任意创建一个图； 2)图的DFS,BFS的递归和非递归算法的实现 3)要求用有向图和无向图

//DFS,无向图+有向图，邻接矩阵实现。 //你的东西太多了。一个一个问吧。而且200分太少了。你这么多种情况。至少也得写8种吧。

#include <string>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <iostream>
#include <set>
#include <math.h>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
const int MAX=210000;
int mat[10][10];
bool vis[10]={false};
void DFS(int s, int n) {
    int i;
    vis[s] = true;
    printf("%d ", s);
    for(i=0; i < n; i++) {
        if(mat[s][i] && !vis[i]) {
            DFS(i, n);
        }
    }
}
int main() {
    int i, n;
    int j;
    n = 10;
    for(i=0; i < n; i++) {
        for(j=0; j < n; j++) {
            mat[i][j] = 1;
        }
    }
    DFS(0, n);
    return 0;
}
推荐文章