グラフ深度最初の検索におけるグレーノードの目的

Question

私が見た深さfirst検索の多くの実装で（例： ここ）、コードは、灰色の頂点（発見されたが、そのすべての隣人が訪問されたわけではない）と黒い頂点（発見され、すべての隣人が訪問された）を区別します。この区別の目的は何ですか？ DFSアルゴリズムは、灰色であろうと黒であろうと、訪問された頂点に訪問しないようです。

Answer 1

DFSを実行する場合、任意のノードは3つの州のいずれかにあります - 訪問する前、その子孫を再帰的に訪問する際、そしてその子孫はすべて訪問された後（その親、すなわち、ラップアップフェーズに戻ります）。 3つの色は3つの状態のそれぞれに対応しています。色と訪問と戻りの色に言及する理由の1つは、より良い理解のためにこれらの区別を明示的に行うことです。

もちろん、これらの色には実際の用途があります。指示されたグラフ$ g $を検討してください。サイクルの存在について$ g $を確認するとします。対象のないグラフでは、検討中のノードに黒または灰色の隣接がある場合、サイクルを示します（そして、DFSはあなたが言及したように訪問しません）。ただし、aの場合 指示 グラフ、黒い隣人はサイクルを意味するものではありません。たとえば、3つの頂点 -$ a、b、$、$ c $のグラフを考えます。 DFSが$ a $から始まり、$ b $、$ c $にアクセスするとします。 $ a $に戻ったとき、$ c $がすでに訪問されており、黒であることをチェックします。しかし、グラフにはサイクルはありません。

指示されたグラフでは、すべての子孫が訪問される前にノードが再び見られる場合にのみ、サイクルが存在します。言い換えれば、ノードに灰色の隣人がいる場合、サイクルがあります（隣人が黒いときではありません）。灰色のノードは、現在その子孫を探索していることを意味します - そして、そのような子孫がこの灰色のノードにエッジを持っている場合、サイクルがあります。したがって、指示されたグラフでサイクル検出するには、3色が必要です。他の例もあるかもしれませんが、アイデアを得る必要があります。

Answer 2

灰色または黒い色を削除できるのはCLRSのエクササイズであり、アルゴリズムはたった2色で正常に機能します。つまり、実際には必要ありません。頂点をマークする主な目標は、すでに訪問された頂点を繰り返し訪問して、無限のループに遭遇しないようにすることです。

DFSアルゴリズムで3色を使用する理由は主に教育的です。概念的にはより明確であり、各ノードの実行中に生徒が何が起こっているかを確認するのに役立ちます。

Answer 3

Gray Vertexは、そのノードにアクセスして、ある順序でその隣人の1つに移動したと述べていますが、そのノードにはより隣接する頂点があるかもしれません。訪問されていない頂点を探索するためにバックトラックするときは便利です。

まあ言ってみれば 頂点Aには2人の隣人BとCがあり、Bには1人の隣接dがあります.

白い色である頂点Aから始めます グレーにします 隣人に横たわります。

アルファベット順の順序を選択することにより、たとえばそれを使用します 頂点b 白い色で、灰色のマークです。

その後、訪問します 白のD->灰色d - >もう隣人はいません。したがって、マーク d->黒.

今、 バックトラック 灰色でbに、そしてもうニーボールはありません。したがって、マーク b->黒.

再び灰色でバックトラックを取り、cマークを訪問します C->灰色 これ以上隣人はCを黒としてマークしません

最後に、Aとマークに戻ります 頂点Aは黒です 白い頂点がなく、すべて黒人のように。

Answer 4

DFSでは、エッジを先端、バックエッジ、クロスエッジ、ツリーエッジとして分類します。

3色を使用してエッジを分類します。そして、これらの色は頂点の状態を表します。つまり、白：頂点Vはまだ発見されていません。

灰色：Vはすでに発見されていますが、Vから到達可能なすべての頂点はまだ発見されていません。したがって、頂点Vはまだスタックにあります。

ブラック：Vはすでにstack.discoveredと終了からポップアウトされています。

DFSを実行すると、エッジEを介して灰色の頂点に遭遇した場合、バックエッジです。エッジEを介して黒い頂点に遭遇した場合、それはクロスエッジ/フォワードエッジです。白い頂点に遭遇した場合、DFSを再帰的に呼び出します。