本文目录一览：
- 1、DFS 递归为什么比非递归要快？？？
- 2、设计一个基于深度优先遍历的算法，判断一个给定的有向图是否包含回路。
- 3、如何将回溯法dfs改写为非递归的
- 4、数据结构图的遍历 1)先任意创建一个图； 2)图的DFS,BFS的递归和非递归算法的实现 3)要求用有向图和无向图
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;
}
/*
*/
