您的位置:

dfs非递归java(DFS非递归算法)

本文目录一览:

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

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

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

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

法一:利用递归方式,在DFS对图进行遍历时,将遍历过的顶点放入栈中,如果新遍历的顶点已经存在于递归栈中,则说明存在一个反向边,即存在一个环。此时栈中结点刚好是环路中的所有结点!

注意该方法没办法用DFS的非递归方法实现,因为非递归方法中,利用出栈的结点获取下一个邻接点入栈,和递归方式不同的地方在于,即使图中有环,非递归方法中的栈也无法存储环上的结点。(DFS的非递归详见本小结后续的代码总结部分)

代码实现如下:

void HasCycle ( Graph G ) {

bool visited [MAX_VERTEX_NUM] ; //访问标记数组

bool recursionStack [MAX_VERTEX_NUM] ; //标记该点是否在栈中

for ( i=0 ; iG.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 ( recusionStack (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 ; iG.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;in;i++)

{

if(mat[s][i]!vis[i])

{

DFS(i,n);

}

}

}

int main()

{   

int i,n;

int j;

n=10;

for(i=0;in;i++)

{

for(j=0;jn;j++)

mat[i][j]=1;

}

DFS(0,n);

    return 0;

/*

*/