本文主要針對(duì)如何判斷有向圖/無(wú)向圖中是否存在環(huán)的問(wèn)題進(jìn)行簡(jiǎn)單的論述。

一 無(wú)向圖

1.利用DFS進(jìn)行判斷

利用DFS判斷有向圖是否存在環(huán)，是最為常用的一種方法，雖然這種方法很常用，但可參考的代碼的實(shí)現(xiàn)比較少，下面對(duì)這種方法及其實(shí)現(xiàn)進(jìn)行詳細(xì)的闡述。

首先，利用DFS判斷無(wú)向圖中是否換的原理是：若在深度優(yōu)先搜索的過(guò)程中遇到回邊(即指向已經(jīng)訪問(wèn)過(guò)的頂點(diǎn)的邊)，則必定存在環(huán)。

所以說(shuō)，是否存在環(huán)的關(guān)鍵在于是否存在滿足條件的“回邊”，那么如何判斷回邊呢？

(1)首先，對(duì)圖中的所有頂點(diǎn)定義三種狀態(tài)：頂點(diǎn)未被訪問(wèn)過(guò)、頂點(diǎn)剛開(kāi)始被訪問(wèn)、頂點(diǎn)被訪問(wèn)過(guò)并且其所有鄰接點(diǎn)也被訪問(wèn)過(guò)。這三種狀態(tài)，在visited數(shù)組中分別用0、1、2來(lái)表示。那么，存在環(huán)的情況可以定義為：在遍歷過(guò)程中，發(fā)現(xiàn)某個(gè)頂點(diǎn)的一條邊指向狀態(tài)1的頂點(diǎn)，此時(shí)就存在環(huán)。

(2)此外，我們要定義一個(gè)father數(shù)組，用以存儲(chǔ)在DFS過(guò)程中頂點(diǎn)的父頂點(diǎn)(或者說(shuō)是生成樹(shù)上的父節(jié)點(diǎn))。其主要作用是為了區(qū)分鄰接點(diǎn)中環(huán)中的頂點(diǎn)和遍歷過(guò)程中的父節(jié)點(diǎn) (單純的用visited數(shù)組無(wú)法區(qū)分)。

整個(gè)過(guò)程的實(shí)現(xiàn)代碼如下：

#define MAX_NUM 100

#define INF 0x7fffffff

/*DFS判斷無(wú)向圖中是否有環(huán)*/

class Graph

{

public:

int vertexNum;//頂點(diǎn)個(gè)數(shù)

int arcNum;//弧的個(gè)數(shù)

int vertex[MAX_NUM];//頂點(diǎn)表

int arc[MAX_NUM][MAX_NUM];//弧信息表

};

int visited[MAX_NUM];//頂點(diǎn)訪問(wèn)表

int father[MAX_NUM];//父節(jié)點(diǎn)表問(wèn)表

void DFS(int v,Graph G)

{

visited[v] = 1;

for(int i = 0 ; i < G.vertexNum; i++)

{

if(i != v && G.arc[v][i] != INF)//鄰接矩陣中節(jié)點(diǎn)v的鄰接點(diǎn)

{

if(visited[i] == 1 && father[i] != v)//不是父節(jié)點(diǎn)，而且還訪問(wèn)過(guò)，說(shuō)明存在環(huán)

{

cout<

int temp = v;

while(temp != i)

{

cout<";//輸出環(huán)

temp = father[temp];

}

cout<

}

else

if(visited[i] == 0)

{

father[i] = v;//更新father數(shù)組

DFS(i,G);

}

}

}

visited[v] = 2;//遍歷完所有的鄰接點(diǎn)才變?yōu)闋顟B(tài)2

}

void DFSTraverse(Graph G)

{

memset(visited,0,sizeof(visited));

memset(father,-1,sizeof(father));

for(int i = 0 ; i < G.vertexNum; i++)

if(!visited[i])

DFS(i,G);

}

由此可見(jiàn)，visited數(shù)組相對(duì)于一般的情況，增加了個(gè)狀態(tài)2，主要是為了防止在回溯過(guò)程中進(jìn)行誤判。所以才能僅用father數(shù)組和狀態(tài)1判斷存在環(huán)。

由于使用的是鄰接矩陣來(lái)存儲(chǔ)，所以該算法的時(shí)間復(fù)雜度為O(n^2),空間復(fù)雜度為O(n)。

2.其他方法本文不再詳述。

二 有向圖

1.拓?fù)渑判?/p>

關(guān)于拓?fù)渑判?#xff0c;資料很多，本文不再詳述。

原文：https://www.cnblogs.com/wangkundentisy/p/9320499.html

總結(jié)

以上是生活随笔為你收集整理的判断图有无环_判断无向图/有向图中是否存在环的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。