實(shí)際上，深度優(yōu)先（或?qū)嶋H上廣度優(yōu)先）搜索還不夠。您需要一個(gè)復(fù)雜得多的算法。

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

    (a)

     |

     |

    (b)

    / \ 

  (d)  |

   |   |

    \ /

    (c)

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

您需要做的是跟蹤訪(fǎng)問(wèn)過(guò)程中的哪些節(jié)點(diǎn)。在上面的示例中，當(dāng)算法到達(dá)（d）時(shí)，它已經(jīng)完成了對(duì)（c）的訪(fǎng)問(wèn)，但沒(méi)有完成對(duì)（a）或（b）的訪(fǎng)問(wèn)。因此，重新訪(fǎng)問(wèn)完成的節(jié)點(diǎn)很好，但是訪(fǎng)問(wèn)未完成的節(jié)點(diǎn)意味著您有一個(gè)周期。通常的做法是為每個(gè)節(jié)點(diǎn)上白色（尚未訪(fǎng)問(wèn)），灰色（正在訪(fǎng)問(wèn)后代）或黑色（完成訪(fǎng)問(wèn)）上色。

這是一些偽代碼！

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

那么只有當(dāng)有一個(gè)循環(huán)（最初所有節(jié)點(diǎn)都應(yīng)該為白色）時(shí)，運(yùn)行visit（root_node）才會(huì)引發(fā)異常。

一個(gè)沒(méi)有周期的連通無(wú)向圖G是一棵樹(shù)！任何一棵樹(shù)都恰好具有n ? 1條邊，因此我們可以簡(jiǎn)單地遍歷圖的邊列表并計(jì)算邊。如果我們計(jì)算n ? 1個(gè)邊，則返回“是”，但是如果到達(dá)第n個(gè)邊，則返回“否”。這需要O（n）時(shí)間，因?yàn)槲覀冏疃嗖榭磏個(gè)邊。

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