在圖中檢測週期（使用三種顏色機制）

Question

我知道如何使用三種顏色（黑色，白色和灰色）機制來檢測圖形中的週期。對於那些誰不知道這一點，請按照此： http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

簡而言之，白色節點是這是未被發現的節點，灰色是其正在處理和黑色節點是被發現的那些節點。

幾天前，一位老人問我爲什麼需要三種顏色才能達到這個目的。爲什麼我們不能只用黑與白呢？爲什麼灰色節點真的需要？我不好意思向他回答這個問題。你們中的任何一個人都可以告訴我他是問我一個有效的問題還是隻是測試我？

Answer 1

不，他沒有測試你。您可以使用兩種顏色在圖表中檢測週期，但在這種情況下圖必須是無向的。
如果您沒有得到原因，請在評論中提問。
編輯
闡述：
我想強調的是，圖是路邊緣的基礎上2種指向，當我們有一個曲線圖，當我們人的邊緣前進以及後退在兩個頂點之間，圖的類型稱爲無向圖。

而下面的圖片是有向圖。

這兩個上紙不同的方式是，我們不畫邊的方向在無向圖中，當我們說存在在無向圖的上下文節點A和B之間的邊緣，它會自動得出爲什麼我們談論反向邊緣，原因在於計算機程序中邊緣以不同表示方式表示的方式，我們僅指示有向邊緣，例如在鄰接列表中，節點B將在A的鄰接列表中只有存在從A到B的邊時，如果需要表明存在從B到A的邊，那麼我們還需要在B的鄰接列表中添加節點A.

類似地，在基於鄰接矩陣的表示的情況下，矩陣關於其前導對角線（從左上開始的對角線）對稱，以示出對於從A存在到B的每條邊，還存在從B到A的邊。
所以要實現我們以下

所以，你該更換無向圖的所有邊後，您會看到計算機的代表圖的實際圖片的任何無向圖。

現在假設你已經被給出了一個圖。你必須問哪一個？

無向圖
我將在參考交談第一張圖片貼在這裏。並假定鄰接表表示已被用來表示圖。

這將是怎樣的？
這裏你可以看到：

A：B - > d - >電子 - > NULL
B：A - > d - >電子 - > NULL
C：d - > NULL
d：一 - >乙 - 「ç - > NULL
E：A - >乙 - > NULL

的目標是設計出一些策略來檢查週期存在與否。
現在假設這些節點代表城市中的一些商店，並且邊緣是道路，所以如果您看到從節點A到B的道路，則自動存在從B到A的道路，因爲圖形是無向的。從鄰接列表中也可以看出這一點。
要檢測無向圖中的一個循環，我們將按照以下過程以一種方式進行，一個典型的程序將遵循。然後你會看到我給出的陳述是有效的。那麼我們開始吧。
我們從節點A開始，以心情遍歷整個圖形，遍歷這裏意味着你想要訪問所有的商店。現在要真正瞭解你訪問過的所有商店，當你離開它們時，你會着色它們，所以你站在節點A，現在你有很多從節點A出現的道路，你可以去其他地方去。所有這些選項都出現在A的鄰接列表中。
假設您選擇一條通往節點B的道路，然後沿着它前進，離開A，在離開A之前着色它。
現在站在B你第一次看到，是節點着色？你看不到！然後你知道你以前沒有訪問過這個節點。再次想要做同樣的事情，所以你看到B的鄰接列表選擇下一條路，你看到一條通向A的路，你再次沿着那條路，在你離開時到達A，B。但是，一旦你到達節點A，你就會看到它被着色，這意味着你之前已經訪問過這家商店，但是後來你意識到，因爲圖形是無向的，所以從B到達A不是問題，因爲邊是雙向的，所以你回溯
爲了避免這種情況再次使用父數組，其中par [i] = j，如果您從j發現i。現在你已經消除了再次訪問父母的陷阱。現在你選擇B的下一條路，這是E，你去那裏，B，這次設置par [E] = B，當你到達E時，你想再次做同樣的事情。但是這一次你看到一條通往A的道路，首先檢查你的父母是？因爲你不想再次拜訪你的父母，因爲你是從那裏來的。
這裏沒有。所以你去了A，但只要你到達A，你就會注意到這個節點是彩色的。
，如果這是真的，那麼這意味着你已經訪問了A，這意味着存在從A再次結束於A的路徑，因此是循環。

那麼告訴我我們使用了多少種顏色？只有兩個，一個是初始顏色，另一個是訪問節點後的顏色。

你可以說我已經在這個特定的例子中展示過它，所以過程可能不會總是起作用，但是嘗試通過遍歷的感覺來實現我描述的情況，並且試着說服自己，如果你從一個節點開始一組道路，如果你到達某處並且看到該節點是有顏色的，這意味着你已經訪問了該節點，並且因爲你避免訪問該節點的父節點，所以你可以看到一個節點着色的唯一方法是由於某個循環。

我讓你知道爲什麼這個東西不能在有向圖中工作，雙向邊的機制在哪裏來到這裏。

Answer 2

這裏是你的解釋，你需要

https://cs.stackexchange.com/questions/9676/the-purpose-of-grey-node-in-graph-depth-first-search

基本上，白色節點變成灰色您訪問後的第一次，但灰色節點變成黑色畢竟只有他們的鄰居變成了黑色，或者他們沒有任何未訪問過的鄰居。

在有向圖中，當且僅當在其所有後代已被訪問之前再次看到一個節點時，存在循環。換句話說，如果一個節點有一個灰色的鄰居，那麼就有一個週期（而不是當鄰居是黑色的時候）。灰色節點意味着我們正在探索它的後代 - 如果一個這樣的後代對這個灰色節點有邊緣，那麼就有一個循環。因此，對於有向圖中的週期檢測，您需要有3種顏色。

現在應該很清楚兩種顏色是不夠的。