为什么深度优先搜索可以判定简单图中是否有环，而宽度优先搜索不行？

一，前言

本文是原创作品，可能有所不足，敬请指正，礼貌交流，感激不尽。

二，前提知识

1，简单图

简单图是指满足以下条件的图：没有连接顶点和其自身的边、不存在平行边。

2，环

这里我们讨论的是简单回路（环），也就是指除了第一个顶点和最后一个顶点相同以外、其他顶点不重复出现的回路。

3，树（单指无向树）的定义是连通无回路的无向图。

约定：

1，以下的“宽搜”二字代表宽度优先搜索，深搜代表深度优先搜索。

2，以下的图均指简单连通图

三，正文

1，首先可以肯定的是，对于无向图而言，宽搜和深搜都能判断是否有环。

简要说明一下，假如一个无向图有环，那么在宽搜的过程中，能搜到已经访问过的结点。如果一个无向图没有环（参考无向树），那么它的宽度优先搜索过程中，是不会访问到已访问过的结点的。

对于深搜，如果一个简单无向图有环，那么深搜的栈保存的结点形成的路径（以下简称深搜结点路径）会有回边（指向栈中结点的边）。但是没有环的话，就不会出现这种情况。

2，对于有向图而言，它们中只有深搜能判断是否有环。

首先对于有向图而言，无论有没有环，宽搜都有可能搜到已访问过的结点。如下图：

当结点B，C都进入了宽搜的队列，那么它们会先后访问D结点，这时就出现了访问已访问过的结点的情况。但是此时该图没有环。 

因此，之前的那个办法不能判断了。

但是深搜依然可以。如果简单有向图中存在环，深搜结点路径依然会出现回边。

四，写在最后

如有错误，敬请指正，礼貌交流，感激不尽

附录，有小伙伴提到了深搜判断无向图是否有环，我写了一下伪代码，逻辑不一定严密，但是大体上应该没错，如有错误，欢迎指正

#include<iostream>
#define N 5
using namespace std;
bool DFS(int node, int tag[],int graph[][5], int parent[])//通过深搜判断无向图是否有环
{//node代表当前结点，tag[i]等于0代表该结点没有在深搜的栈中，tag[i]等于1代表当前结点在深搜的栈中。
//graph数组代表图的邻接矩阵，N代表结点个数，
//parent[i]等于j，代表当前深搜的栈中结点i的前驱是j ,也即访问i之后就立马访问j了 
//该函数返回false代表有环，否则代表无环 if(tag[node] == 1)return false;//遇到回边就返回false else tag[node] = 1;bool res = true;for(int i=0;i<N;i++){if(graph[node][i] > 0 && parent[node] != i)//如果结点node和i之间存在一条边,当前结点的父节点不应该访问 {parent[i] = node;res = DFS( i,  tag, graph, parent);if(res == false)break;//只要有一条回边，就代表整个图有环 parent[i] = -1;tag[i] = 0; } }return res;
} 
int main()
{return 0;
}