查找有向图中的环
部分引自http://blog.csdn.net/xw13106209/article/details/6538634
有向圖：
主要有深度優(yōu)先和拓?fù)渑判?中方法
1、拓?fù)渑判?#xff0c;如果能夠用拓?fù)渑判蛲瓿蓪?duì)圖中所有節(jié)點(diǎn)的排序的話，就說(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)有被訪問(wèn)過(guò)
??? -1，被訪問(wèn)過(guò)至少1次，其后代節(jié)點(diǎn)正在被訪問(wèn)中
??? 1，其后代節(jié)點(diǎn)都被訪問(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ō)明是在訪問(wèn)該節(jié)點(diǎn)的后代的過(guò)程中訪問(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)的路徑
無(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)。
?????i)如果m>=n，則根據(jù)圖論知識(shí)可直接判斷存在環(huán)路。（證明：如果沒(méi)有環(huán)路，則該圖必然是k棵樹(shù) k>=1。根據(jù)樹(shù)的性質(zhì)，邊的數(shù)目m = n-k。k>=1，所以：m<n）? ? ? ? ? ? ??
? ?? ii)如果m<n 則按照上面的算法每刪除一個(gè)度為0的頂點(diǎn)操作一次（最多n次），或每刪除一個(gè)度為1的頂點(diǎn)（同時(shí)刪一條邊）操作一次（最多m次）。這兩種操作的總數(shù)不會(huì)超過(guò)m+n。由于m<n，所以算法復(fù)雜度為O(n)。
- 注：
?????該方法，算法復(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)。
方法3：
摘自：http://blog.csdn.net/lzrzhao/archive/2008/03/13/2175787.aspx
PS：此方法于2011-6-12補(bǔ)充
假定：圖頂點(diǎn)個(gè)數(shù)為M，邊條數(shù)為E
遍歷一遍，判斷圖分為幾部分（假定為P部分，即圖有 P 個(gè)連通分量） 對(duì)于每一個(gè)連通分量，如果無(wú)環(huán)則只能是樹(shù)，即：邊數(shù)＝結(jié)點(diǎn)數(shù)－1 只要有一個(gè)滿(mǎn)足 ?? ? 邊數(shù) ? > ? 結(jié)點(diǎn)數(shù)－1
原圖就有環(huán)
將P個(gè)連通分量的不等式相加，就得到： P1:E1=M1-1 P2:E2=M2-1 ... PN:EN>MN-1 所有邊數(shù)(E) ? > ? 所有結(jié)點(diǎn)數(shù)(M) -?連通分量個(gè)數(shù)(P)
即： ?E?+?P?>?M? 所以只要判斷結(jié)果??E? +?P?>?M?就表示原圖有環(huán)，否則無(wú)環(huán).實(shí)例代碼如下：
如果要將有向圖中的環(huán)輸出：
bool Decoder::FindCycle(std::vector<vector<double> > &g, std::vector<int> &c) {int size = g.size();vector<int> color(size,0);//所有的結(jié)點(diǎn)都沒(méi)有被訪問(wèn)。當(dāng)i結(jié)點(diǎn)為0,未被訪問(wèn);i為-1，環(huán)；i為1，i的所有后裔結(jié)點(diǎn)都被訪問(wèn)過(guò)//for (int i=0;i<size;++i)for (int i= size -1;i>=0;--i){if(color[i]==0){color[i] = -1;if(Dfs(g,color,c,i)){//c.push_back(i);return true;}}}return false; }bool Decoder::Dfs(std::vector<vector<double> > &g, std::vector<int> &color, std::vector<int> &c,int i)//如果有返回到i的環(huán)，則true;否則，false.遍歷結(jié)點(diǎn)i的所有后繼 {int size = g.size();for (int j=0;j<size;++j){if (g[i][j] !=noEdge){if(color[j]==0){color[j] = -1;if(Dfs(g,color,c,j)){//c.push_back(j);return true;}}else if(color[j] == -1){c.push_back(j);int start = j;for (int ind = 0;ind <size ;++ind)//復(fù)雜度太高了，應(yīng)該記錄一個(gè)parent表{if(g[start][ind] !=noEdge && color[ind] == -1){if(ind == j)break;c.push_back(ind);start = ind;}}return true;}}}color[i] = 1;return false; }
用拓?fù)渑判虿檎矣邢驁D的環(huán)有如下的缺點(diǎn)
http://hi.baidu.com/hpc_robot/blog/item/c21ade979489d86855fb96f2.html
總結(jié)
- 上一篇： 图论的一些资料
- 下一篇： windows下配置java