c語言，無向圖如何檢測是否有環(huán)？有深度優(yōu)先和拓撲排序方法來確定有向圖是否有環(huán)。1. 拓撲排序，如果可以用拓撲排序來完成對圖中所有節(jié)點的排序，則表示圖中沒有環(huán)，如果不能完成，則表示有環(huán)。2、強連通分量。

c語言，無向圖如何檢測是否有環(huán)？

有深度優(yōu)先和拓撲排序方法來確定有向圖是否有環(huán)。

1. 拓撲排序，如果可以用拓撲排序來完成對圖中所有節(jié)點的排序，則表示圖中沒有環(huán)，如果不能完成，則表示有環(huán)。

2、強連通分量。我們可以回憶一下強連通子圖的概念，也就是說，對于一個圖的子圖，子圖中的任何U->V必須有V->U，那么它就是一個強連通子圖。這個限制正是環(huán)的概念。所以我認為，通過尋找圖的強連通子圖，我們應(yīng)該能夠找出圖中是否有環(huán)，以及有多少環(huán)。

3. 改進的DFS不能僅由DFS使用。如果問題是一個無向圖，那么DFS可以被解決。但無向圖不能得到正確的結(jié)果。例如：a->B，a->C->B，我們用DFS來處理這個圖，我們會發(fā)現(xiàn)它有環(huán)，但它沒有。我們可以通過稍微改變DFS來解決這個問題。解決方法如下：圖中的一個節(jié)點，根據(jù)其C[n]值，有三種狀態(tài)：0，該節(jié)點未被訪問-1，至少被訪問過一次，其子節(jié)點正在被訪問，1，其子節(jié)點已被訪問。根據(jù)這個假設(shè)，當(dāng)根據(jù)DFS進行搜索時，有三種可能：1。如果C[v]=0，則它是一個新節(jié)點，不會被處理。2如果C[v]=-1，則表示在訪問節(jié)點的子節(jié)點的過程中訪問了節(jié)點本身，則圖中存在一個環(huán)。三。如果C[v]=1，類似于2的導(dǎo)數(shù)，則不存在環(huán)。在程序中加入一些特殊的處理，即在圖中找出幾個環(huán)并記錄每個環(huán)的路徑