一，前言
本文是原創(chuàng)作品，可能有所不足，敬請指正，禮貌交流，感激不盡。
二，前提知識
1，簡單圖
簡單圖是指滿足以下條件的圖：沒有連接頂點和其自身的邊、不存在平行邊。
2，環(huán)
這里我們討論的是簡單回路（環(huán)），也就是指除了第一個頂點和最后一個頂點相同以外、其他頂點不重復(fù)出現(xiàn)的回路。
3，樹（單指無向樹）的定義是連通無回路的無向圖。
約定：
1，以下的“寬搜”二字代表寬度優(yōu)先搜索，深搜代表深度優(yōu)先搜索。
2，以下的圖均指簡單連通圖
三，正文
1，首先可以肯定的是，對于無向圖而言，寬搜和深搜都能判斷是否有環(huán)。
簡要說明一下，假如一個無向圖有環(huán)，那么在寬搜的過程中，能搜到已經(jīng)訪問過的結(jié)點。如果一個無向圖沒有環(huán)（參考無向樹），那么它的寬度優(yōu)先搜索過程中，是不會訪問到已訪問過的結(jié)點的。
對于深搜，如果一個簡單無向圖有環(huán)，那么深搜的棧保存的結(jié)點形成的路徑（以下簡稱深搜結(jié)點路徑）會有回邊（指向棧中結(jié)點的邊）。但是沒有環(huán)的話，就不會出現(xiàn)這種情況。
2，對于有向圖而言，它們中只有深搜能判斷是否有環(huán)。
首先對于有向圖而言，無論有沒有環(huán)，寬搜都有可能搜到已訪問過的結(jié)點。如下圖：
當(dāng)結(jié)點B，C都進(jìn)入了寬搜的隊列，那么它們會先后訪問D結(jié)點，這時就出現(xiàn)了訪問已訪問過的結(jié)點的情況。但是此時該圖沒有環(huán)。?
因此，之前的那個辦法不能判斷了。
但是深搜依然可以。如果簡單有向圖中存在環(huán)，深搜結(jié)點路徑依然會出現(xiàn)回邊。文章來源：http://www.zghlxwxcb.cn/news/detail-629292.html
四，寫在最后
如有錯誤，敬請指正，禮貌交流，感激不盡
附錄，有小伙伴提到了深搜判斷無向圖是否有環(huán)，我寫了一下偽代碼，邏輯不一定嚴(yán)密，但是大體上應(yīng)該沒錯，如有錯誤，歡迎指正文章來源地址http://www.zghlxwxcb.cn/news/detail-629292.html
#include<iostream>
#define N 5
using namespace std;
bool DFS(int node, int tag[],int graph[][5], int parent[])//通過深搜判斷無向圖是否有環(huán)
{//node代表當(dāng)前結(jié)點，tag[i]等于0代表該結(jié)點沒有在深搜的棧中，tag[i]等于1代表當(dāng)前結(jié)點在深搜的棧中。
//graph數(shù)組代表圖的鄰接矩陣，N代表結(jié)點個數(shù)，
//parent[i]等于j，代表當(dāng)前深搜的棧中結(jié)點i的前驅(qū)是j ,也即訪問i之后就立馬訪問j了
//該函數(shù)返回false代表有環(huán)，否則代表無環(huán)
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)//如果結(jié)點node和i之間存在一條邊,當(dāng)前結(jié)點的父節(jié)點不應(yīng)該訪問
{
parent[i] = node;
res = DFS( i, tag, graph, parent);
if(res == false)break;//只要有一條回邊，就代表整個圖有環(huán)
parent[i] = -1;
tag[i] = 0;
}
}
return res;
}
int main()
{
return 0;
} 到了這里，關(guān)于為什么深度優(yōu)先搜索可以判定簡單圖中是否有環(huán)，而寬度優(yōu)先搜索不行？的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
