判斷一個圖是否有環(huán)無向圖有向圖

1、一、無向圖：方法1：· 如果存在回路，則必存在一個子圖，是一個環(huán)路。環(huán)路中所有頂點的度>=2。  · n算法：     第一步：刪除所有度<=1的頂點及相關的邊，并將另外與這些邊相關的其它頂點的度減一。       第二步：將度數(shù)變?yōu)?的頂點排入隊列，并從該隊列中取出一個頂點重復步驟一。       如果最后還有未刪除頂點，則存在環(huán)，否則沒有環(huán)。  · n

2、算法分析：       由于有m條邊，n個頂點。     i)如果m>=n，則根據(jù)圖論知識可直接判斷存在環(huán)路。（證明：如果沒有環(huán)路，則該圖必然是k棵樹 k>=1。根據(jù)樹的性質(zhì)，邊的數(shù)目m = n-k。k>=1，所以：m<n）                   ii)如果m<n 則按照上面的算法每刪除一個度為0的頂點操作一次（最多n次），或每刪除一

3、個度為1的頂點（同時刪一條邊）操作一次（最多m次）。這兩種操作的總數(shù)不會超過m+n。由于m<n，所以算法復雜度為O(n)。· 注：     該方法，算法復雜度不止O(V)，首先初始時刻統(tǒng)計所有頂點的度的時候，復雜度為(V + E)，即使在后來的循環(huán)中E>=V，這樣算法的復雜度也只能為O(V + E)。其次，在每次循環(huán)時，刪除度為1的頂點，那么就必須將與這個頂點相連的點的度減一，并且執(zhí)行delete node from listlistnode，這里查找的復雜度為listlistnode的長度，只有這樣才能保證當degree

4、i=1時，listi里面只有一個點。這樣最差的復雜度就為O(EV)了。方法2：DFS搜索圖，圖中的邊只可能是樹邊或反向邊，一旦發(fā)現(xiàn)反向邊，則表明存在環(huán)。該算法的復雜度為O(V)。方法3：摘自：PS：此方法于2011-6-12補充假定：圖頂點個數(shù)為M，邊條數(shù)為E遍歷一遍，判斷圖分為幾部分（假定為P部分，即圖有 P 個連通分量）對于每一個連通分量，如果無環(huán)則只能是樹，即：邊數(shù)結點數(shù)1只要有一個滿足      邊數(shù)   >   結點數(shù)1原圖就有環(huán)將P個連通分量的不等式相加，就得到：P1:E1=M1-1P2:E2=M2-1.PN:EN>MN

5、-1    所有邊數(shù)(E)   >   所有結點數(shù)(M) - 連通分量個數(shù)(P)即：  E + P > M  所以只要判斷結果  E  + P > M 就表示原圖有環(huán)，否則無環(huán).實例代碼如下：1. #include<iostream>  2. #include<malloc.h>  3. using nam

6、espace std;  4. #define maxNum 100 /定義鄰接舉證的最大定點數(shù)  5. int visitedmaxNum;/通過visited數(shù)組來標記這個頂點是否被訪問過，0表示未被訪問，1表示被訪問  6. int DFS_Count;/連通部件個數(shù)，用于測試無向圖是否連通，DFS_Count=1表示只有一個連通部件，所以整個無向圖是連通的  7. int premaxNum;  8. int 

7、;postmaxNum;  9. int point;/pre和post的值  10.   11. /圖的鄰接矩陣表示結構  12. typedef struct  13.   14.     char vmaxNum;/圖的頂點信息  15.     int emaxNummaxNum;/圖的頂點信息  16. &#

8、160;   int vNum;/頂點個數(shù)  17.     int eNum;/邊的個數(shù)  18. graph;  19. void createGraph(graph *g);/創(chuàng)建圖g  20. void DFS(graph *g);/深度優(yōu)先遍歷圖g  21. void dfs(graph *g,int i);/從頂點i開始深度優(yōu)

9、先遍歷與其相鄰的點  22. void dfs(graph *g,int i)  23.   24.     /cout<<"頂點"<<g->vi<<"已經(jīng)被訪問"<<endl;  25.     cout<<"頂點"<<i<<"已經(jīng)被訪問"

10、;<<endl;  26.     visitedi=1;/標記頂點i被訪問  27.     prei=+point;  28.     for(int j=1;j<=g->vNum;j+)  29.       30.        

11、; if(g->eij!=0&&visitedj=0)  31.             dfs(g,j);  32.       33.     posti=+point;  34.   35.   36. void DFS(graph

12、 *g)  37.   38.     int i;  39.     /初始化visited數(shù)組，表示一開始所有頂點都未被訪問過  40.     for(i=1;i<=g->vNum;i+)  41.       42.      &

13、#160;  visitedi=0;  43.         prei=0;  44.         posti=0;  45.       46.     /初始化pre和post  47.    

14、60;point=0;  48.     /初始化連通部件數(shù)為0  49.     DFS_Count=0;  50.     /深度優(yōu)先搜索  51.     for(i=1;i<=g->vNum;i+)  52.       53.   

15、60;     if(visitedi=0)/如果這個頂點為被訪問過，則從i頂點出發(fā)進行深度優(yōu)先遍歷  54.           55.             DFS_Count+;/統(tǒng)計調(diào)用void dfs(graph *g,int i);的次數(shù)  56

16、.             dfs(g,i);  57.           58.       59.   60. void createGraph(graph *g)/創(chuàng)建圖g  61.   62.  &#

17、160;  cout<<"正在創(chuàng)建無向圖."<<endl;  63.     cout<<"請輸入頂點個數(shù)vNum:"  64.     cin>>g->vNum;  65.     cout<<"請輸入邊的個數(shù)eNum:"  66.  

18、60;  cin>>g->eNum;  67.     int i,j;  68.     /輸入頂點信息  69.     /cout<<"請輸入頂點信息："<<endl;  70.     /for(i=0;i<g->vNum;i+) 

19、60;71.     /  cin>>g->vi;  72.     /初始畫圖g  73.     for(i=1;i<=g->vNum;i+)  74.         for(j=1;j<=g->vNum;j+)  75.   &#

20、160;         g->eij=0;  76.     /輸入邊的情況  77.     cout<<"請輸入邊的頭和尾"<<endl;  78.     for(int k=0;k<g->eNum;k+)  79.  

21、     80.         cin>>i>>j;  81.         g->eij=1;  82.         g->eji=1;/無向圖對稱  83.    

22、0;  84.   85. int main()  86.   87.     graph *g;  88.     g=(graph*)malloc(sizeof(graph);  89.     createGraph(g);/創(chuàng)建圖g  90.     DFS(g);/深度

23、優(yōu)先遍歷  91.     /連通部件數(shù)，用于判斷是否連通圖  92.     cout<<"連通部件數(shù)量："  93.     cout<<DFS_Count<<endl;  94.     if(DFS_Count=1)  95.     

24、    cout<<"圖g是連通圖"<<endl;  96.     else if(DFS_Count>1)  97.         cout<<"圖g不是連通圖"<<endl;  98.     /各頂點的pre和post值

25、60; 99.     for(int i=1;i<=g->vNum;i+)  100.         cout<<"頂點"<<i<<"的pre和post分別為："<<prei<<" "<<posti<<endl;  101.   

26、  /cout<<endl;  102.     /判斷無向圖中是否有環(huán)  103.     if(g->eNum+DFS_Count>g->vNum)  104.         cout<<"圖g中存在環(huán)"<<endl;  105.   &#

27、160; else  106.         cout<<"圖g中不存在環(huán)"<<endl;  107.     int k;  108.     cin>>k;  109.     return 0;  110.

28、   111. /* 112. 輸入： 113. 正在創(chuàng)建無向圖. 114. 請輸入頂點個數(shù)vNum:10 115. 請輸入邊的個數(shù)eNum:9 116. 請輸入邊的頭和尾 117. 1 2 118. 1 4 119. 2 5 120. 2 6 121. 4 7 122. 5 9 123. 6 3 124. 7 8 125. 9 10 1

29、26. */  注意：有向圖不能使用此方法。比如1->2,1-3,2->3,4->5，如果使用上述方法會判定為含有還，但并非如此。二、有向圖：主要有深度優(yōu)先和拓撲排序2中方法1、拓撲排序，如果能夠用拓撲排序完成對圖中所有節(jié)點的排序的話，就說明這個圖中沒有環(huán)，而如果不能完成，則說明有環(huán)。2、可以用Strongly Connected Components來做，我們可以回憶一下強連通子圖的概念，就是說對于一個圖的某個子圖，該子圖中的任意u->v,必有v->u，則這是一個強連通子圖。這個限定正好是環(huán)的概念。所以我想，通過尋找圖的強連通子圖的方法應該可

30、以找出一個圖中到底有沒有環(huán)、有幾個環(huán)。3、就是用一個改進的DFS    剛看到這個問題的時候，我想單純用DFS就可以解決問題了。但細想一下，是不能夠的。如果題目給出的是一個無向圖，那么OK，DFS是可以解決的。但無向圖得不出正確結果的。比如：A->B,A->C->B,我們用DFS來處理這個圖，我們會得出它有環(huán)，但其實沒有。    我們可以對DFS稍加變化，來解決這個問題。解決的方法如下：    圖中的一個節(jié)點，根據(jù)其CN的值，有三種狀態(tài)：    0，此節(jié)點沒

31、有被訪問過    -1，被訪問過至少1次，其后代節(jié)點正在被訪問中    1，其后代節(jié)點都被訪問過。    按照這樣的假設，當按照DFS進行搜索時，碰到一個節(jié)點時有三種可能：    1、如果CV=0，這是一個新的節(jié)點，不做處理    2、如果CV=-1，說明是在訪問該節(jié)點的后代的過程中訪問到該節(jié)點本身，則圖中有環(huán)。    3、如果CV=1，類似于2的推導，沒有環(huán)。    在程序中加上一些特

32、殊的處理，即可以找出圖中有幾個環(huán)，并記錄每個環(huán)的路徑PS：此代碼實現(xiàn)于2011-6-13補充改進DFS算法代碼示例（判斷是否是一個有向無環(huán)圖）1. #include<iostream>  2. #include<malloc.h>  3. using namespace std;  4. #define maxNum 100 /定義鄰接舉證的最大定點數(shù)  5. int premaxNum;  6. int

33、0;postmaxNum;  7. int point=0;/pre和post的值  8. bool is_DAG=true;/標識位，表示有向無環(huán)圖  9. /* 10. 頂點顏色表 coloru 11.  0 白色，未被訪問過的節(jié)點標白色 12.  -1 灰色，已經(jīng)被訪問過一次的節(jié)點標灰色 13.  1 黑色，當該節(jié)點的所有后代都被訪問過標黑色 14. 反向邊： 15.  

34、如果第一次訪問(u,v)時v為灰色，則(u,v)為反向邊。在對圖的深度優(yōu)先搜索中沒有發(fā)現(xiàn) 16.  反向邊，則該圖沒有回路 17. 程序判斷依據(jù)： 18.     仍然是按圖的節(jié)點深度遍歷，訪問到V時，V若被訪問過，那么有2種狀態(tài)： 19.     coloru=-1，程序跳出，存在環(huán) 20.     coloru=1，程序繼續(xù)，這不是環(huán) 21. 時間復雜度：O(n+e) 22. */ 

35、 23. int colormaxNum;/頂點顏色表 coloru  24. /圖的鄰接矩陣表示結構  25. typedef struct  26.   27.     char vmaxNum;/圖的頂點信息  28.     int emaxNummaxNum;/圖的頂點信息  29.    

36、0;int vNum;/頂點個數(shù)  30.     int eNum;/邊的個數(shù)  31. graph;  32. void createGraph(graph *g);/創(chuàng)建圖g  33. void DFS(graph *g);/深度優(yōu)先遍歷圖g  34. void dfs(graph *g,int i);/從頂點i開始深度優(yōu)先遍歷與其相鄰的點  

37、;35. void dfs(graph *g,int i)  36.   37.     /cout<<"頂點"<<g->vi<<"已經(jīng)被訪問"<<endl;  38.     cout<<"頂點"<<i<<"已經(jīng)被訪問"<<endl; 

38、 39.     colori=-1;  40.     prei=+point;  41.     for(int j=1;j<=g->vNum;j+)  42.       43.         if(g->eij!=0) &

39、#160;44.              45.             if(colorj=-1)/探索到回邊,存在環(huán)  46.               47.  

40、0;              is_DAG=false;/不是有向無環(huán)圖  48.               49.             else if(colo

41、rj=0)  50.                 dfs(g,j);  51.           52.       53.     posti=+point;  54. &

42、#160;   colori=1;/表示i的后裔節(jié)點都被訪問過  55.   56. void DFS(graph *g)  57.   58.     int i;  59.     /初始化color數(shù)組，表示一開始所有頂點都未被訪問過，/初始化pre和post  60.     for(i=1

43、;i<=g->vNum;i+)  61.       62.         colori=0;  63.         prei=0;  64.         posti=0;  65.  &

44、#160;    66.     /深度優(yōu)先搜索  67.     for(i=1;i<=g->vNum;i+)  68.       69.         if(colori=0)/如果這個頂點為被訪問過，則從i頂點出發(fā)進行深度優(yōu)先遍歷  70.  &#

45、160;        71.             dfs(g,i);  72.               73.           

46、;74.       75.   76. void createGraph(graph *g)/創(chuàng)建圖g  77.   78.     cout<<"正在創(chuàng)建無向圖."<<endl;  79.     cout<<"請輸入頂點個數(shù)vNum:"  80.  

47、;   cin>>g->vNum;  81.     cout<<"請輸入邊的個數(shù)eNum:"  82.     cin>>g->eNum;  83.     int i,j;  84.     /初始畫圖g  85.  

48、   for(i=1;i<=g->vNum;i+)  86.         for(j=1;j<=g->vNum;j+)  87.             g->eij=0;  88.     /輸入邊的情況  89.

49、     cout<<"請輸入邊的頭和尾"<<endl;  90.     for(int k=1;k<=g->eNum;k+)  91.       92.         cin>>i>>j;  93.