實際上，深度優(yōu)先（或實際上廣度優(yōu)先）搜索還不夠。您需要一個復雜得多的算法。

例如，假設有一個圖，它的節(jié)點為{a，b，c，d}，而邊為{（a，b），（b，c），（b，d），（d，c）}的邊為（x ，y）是從x到y(tǒng)的邊。（看起來像這樣，所有邊緣都朝下。）

    (a)

     |

     |

    (b)

    / \ 

  (d)  |

   |   |

    \ /

    (c)

然后進行深度優(yōu)先搜索可能會訪問節(jié)點（a），然后訪問（b），然后訪問（c），然后回溯到（b），然后訪問（d），最后再次訪問（c），并得出一個循環(huán)-沒有的時候。廣度優(yōu)先發(fā)生類似的事情。

您需要做的是跟蹤訪問過程中的哪些節(jié)點。在上面的示例中，當算法到達（d）時，它已經完成了對（c）的訪問，但沒有完成對（a）或（b）的訪問。因此，重新訪問完成的節(jié)點很好，但是訪問未完成的節(jié)點意味著您有一個周期。通常的做法是為每個節(jié)點上白色（尚未訪問），灰色（正在訪問后代）或黑色（完成訪問）上色。

這是一些偽代碼！

define visit(node n):

  if n.colour == grey: //if we're still visiting this node or its descendants

    throw exception("Cycle found")

  n.colour = grey //to indicate this node is being visited

  for node child in n.children():

    if child.colour == white: //if the child is unexplored

      visit(child)

  n.colour = black //to show we're done visiting this node

  return

那么只有當有一個循環(huán)（最初所有節(jié)點都應該為白色）時，運行visit（root_node）才會引發(fā)異常。

一個沒有周期的連通無向圖G是一棵樹！任何一棵樹都恰好具有n ? 1條邊，因此我們可以簡單地遍歷圖的邊列表并計算邊。如果我們計算n ? 1個邊，則返回“是”，但是如果到達第n個邊，則返回“否”。這需要O（n）時間，因為我們最多查看n個邊。

但是，如果圖形未連接，那么我們將不得不使用DFS。我們可以遍歷這些邊，如果有任何未探索的邊通向被訪問的頂點，則它具有循環(huán)。