無(wú)向圖：

法1：

如果存在回路，則必存在一個(gè)子圖，是一個(gè)環(huán)路。環(huán)路中所有頂點(diǎn)的度>=2。

n算法：

第一步：刪除所有度<=1的頂點(diǎn)及相關(guān)的邊，并將另外與這些邊相關(guān)的其它頂點(diǎn)的度減一。

第二步：將度數(shù)變?yōu)?的頂點(diǎn)排入隊(duì)列，并從該隊(duì)列中取出一個(gè)頂點(diǎn)重復(fù)步驟一。

如果最后還有未刪除頂點(diǎn)，則存在環(huán)，否則沒(méi)有環(huán)。

n算法分析：

由于有m條邊，n個(gè)頂點(diǎn)。如果m>=n，則根據(jù)圖論知識(shí)可直接判斷存在環(huán)路。

(證明：如果沒(méi)有環(huán)路，則該圖必然是k棵樹(shù)?k>=1。根據(jù)樹(shù)的性質(zhì)，邊的數(shù)目m?=?n-k。k>=1，所以：m

如果m

另：

該方法，算法復(fù)雜度不止O(V)，首先初始時(shí)刻統(tǒng)計(jì)所有頂點(diǎn)的度的時(shí)候，復(fù)雜度為(V + E)，即使在后來(lái)的循環(huán)中E>=V，這樣算法的復(fù)雜度也只能為O(V + E)。其次，在每次循環(huán)時(shí)，刪除度為1的頂點(diǎn)，那么就必須將與這個(gè)頂點(diǎn)相連的點(diǎn)的度減一，并且執(zhí)行delete node from list[list[node]]，這里查找的復(fù)雜度為list[list[node]]的長(zhǎng)度，只有這樣才能保證當(dāng)degree[i]=1時(shí)，list[i]里面只有一個(gè)點(diǎn)。這樣最差的復(fù)雜度就為O(EV)了。

法2：

DFS搜索圖，圖中的邊只可能是樹(shù)邊或反向邊，一旦發(fā)現(xiàn)反向邊，則表明存在環(huán)。該算法的復(fù)雜度為O(V)。

有向圖：

主要有深度優(yōu)先和拓?fù)渑判?中方法

1、拓?fù)渑判?#xff0c;如果能夠用拓?fù)渑判蛲瓿蓪?duì)圖中所有節(jié)點(diǎn)的排序的話(huà)，就說(shuō)明這個(gè)圖中沒(méi)有環(huán)，而如果不能完成，則說(shuō)明有環(huán)。

2、可以用Strongly Connected Components來(lái)做，我們可以回憶一下強(qiáng)連通子圖的概念，就是說(shuō)對(duì)于一個(gè)圖的某個(gè)子圖，該子圖中的任意u->v,必有v->u，則這是一個(gè)強(qiáng)連通子圖。這個(gè)限定正好是環(huán)的概念。所以我想，通過(guò)尋找圖的強(qiáng)連通子圖的方法應(yīng)該可以找出一個(gè)圖中到底有沒(méi)有環(huán)、有幾個(gè)環(huán)。

3、就是用一個(gè)改進(jìn)的DFS

剛看到這個(gè)問(wèn)題的時(shí)候，我想單純用DFS就可以解決問(wèn)題了。但細(xì)想一下，是不能夠的。如果題目給出的是一個(gè)無(wú)向圖，那么OK，DFS是可以解決的。但無(wú)向圖得不出正確結(jié)果的。比如：A->B,A->C->B,我們用DFS來(lái)處理這個(gè)圖，我們會(huì)得出它有環(huán)，但其實(shí)沒(méi)有。

我們可以對(duì)DFS稍加變化，來(lái)解決這個(gè)問(wèn)題。解決的方法如下：

圖中的一個(gè)節(jié)點(diǎn)，根據(jù)其C[N]的值，有三種狀態(tài)：

0，此節(jié)點(diǎn)沒(méi)有被訪(fǎng)問(wèn)過(guò)

-1，被訪(fǎng)問(wèn)過(guò)至少1次，其后代節(jié)點(diǎn)正在被訪(fǎng)問(wèn)中

1，其后代節(jié)點(diǎn)都被訪(fǎng)問(wèn)過(guò)。

按照這樣的假設(shè)，當(dāng)按照DFS進(jìn)行搜索時(shí)，碰到一個(gè)節(jié)點(diǎn)時(shí)有三種可能：

1、如果C[V]=0，這是一個(gè)新的節(jié)點(diǎn)，不做處理

2、如果C[V]=-1，說(shuō)明是在訪(fǎng)問(wèn)該節(jié)點(diǎn)的后代的過(guò)程中訪(fǎng)問(wèn)到該節(jié)點(diǎn)本身，則圖中有環(huán)。

3、如果C[V]=1，類(lèi)似于2的推導(dǎo)，沒(méi)有環(huán)。??? 在程序中加上一些特殊的處理，即可以找出圖中有幾個(gè)環(huán)，并記錄每個(gè)環(huán)的路徑

總結(jié)

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

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