一，前言
本文是原创作品，可能有所不足，敬请指正，礼貌交流，感激不尽。
二，前提知识
1，简单图
简单图是指满足以下条件的图：没有连接顶点和其自身的边、不存在平行边。
2，环
这里我们讨论的是简单回路（环），也就是指除了第一个顶点和最后一个顶点相同以外、其他顶点不重复出现的回路。
3，树（单指无向树）的定义是连通无回路的无向图。
约定：
1，以下的“宽搜”二字代表宽度优先搜索，深搜代表深度优先搜索。
2，以下的图均指简单连通图
三，正文
1，首先可以肯定的是，对于无向图而言，宽搜和深搜都能判断是否有环。
简要说明一下，假如一个无向图有环，那么在宽搜的过程中，能搜到已经访问过的结点。如果一个无向图没有环（参考无向树），那么它的宽度优先搜索过程中，是不会访问到已访问过的结点的。
对于深搜，如果一个简单无向图有环，那么深搜的栈保存的结点形成的路径（以下简称深搜结点路径）会有回边（指向栈中结点的边）。但是没有环的话，就不会出现这种情况。
2，对于有向图而言，它们中只有深搜能判断是否有环。
首先对于有向图而言，无论有没有环，宽搜都有可能搜到已访问过的结点。如下图：
当结点B，C都进入了宽搜的队列，那么它们会先后访问D结点，这时就出现了访问已访问过的结点的情况。但是此时该图没有环。
因此，之前的那个办法不能判断了。
但是深搜依然可以。如果简单有向图中存在环，深搜结点路径依然会出现回边。文章来源：https://www.toymoban.com/news/detail-629292.html
四，写在最后
如有错误，敬请指正，礼貌交流，感激不尽
附录，有小伙伴提到了深搜判断无向图是否有环，我写了一下伪代码，逻辑不一定严密，但是大体上应该没错，如有错误，欢迎指正文章来源地址https://www.toymoban.com/news/detail-629292.html
#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;
} 到了这里，关于为什么深度优先搜索可以判定简单图中是否有环，而宽度优先搜索不行？的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
