深さ優先ツリーには、ツリーを定義するエッジ（つまり、で使用されたエッジ）があります。トラバーサル）。
他のノードのいくつかを接続するいくつかの残りのエッジがあります。クロスエッジとフォワードエッジの違いは何ですか？
ウィキペディアから：
このスパニングツリーに基づいて、エッジ元のグラフのは、3つのクラスに分類できます。ツリーのノードからその子孫の1つを指す前縁、ノードからその祖先の1つを指す後縁、およびどちらもしないクロスエッジです。スパニングツリー自体に属するエッジであるツリーエッジは、前方エッジとは別に分類される場合があります。元のグラフが無向の場合、そのエッジはすべてツリーエッジまたはバックエッジです。
トラバーサルで使用されていないエッジではありません。あるノードから別のノードへのポイントは親子関係を確立しますか？
コメント
- 関連： cs.stackexchange.com/questions/99988/ … は、有向グラフの場合、クロスエッジではなくフォワードエッジを作成することを好むアルゴリズムの確立を目指しています。深度優先検索。
回答
ウィキペディアに回答があります：
すべてのタイプのエッジがこの図に表示されます。このグラフでDFSをトレースし（ノードは番号順に探索されます）、どこにあるかを確認します。直感は失敗します。
これは図を説明します：-
前縁：（u、v）、ここでvはuの子孫ですが、木の端ではありません。それは非ツリーエッジです頂点をDFSツリーの子孫に接続します。
クロスエッジ：その他のエッジ。同じ深さ優先ツリーまたは異なる深さ優先ツリーの頂点間を移動できます。 （素人）
グラフGの他のエッジです。2つの異なるDFSツリー内の頂点または同じDFSツリー内の2つの頂点を接続しますが、どちらも他方の祖先ではありません。（正式）
コメント
- 6を最初に（右側を最初に）トラバースすることが不可能ではないのはなぜですか？それが起こった場合、2- > 3エッジは何と呼ばれていましたか？
- @soandos、時間をかけてアルゴリズムをトレースすることをお勧めします。ウィキペディアンが'間違いを犯さなかったと仮定すると、画像はこのグラフでのDFSの真正な実行を示しているため、アルゴリズムをこのトレースに適合させる方法があります。エッジのタイプはウィキペディアで十分に明確に説明されており、この例も参照できます。
- これがDFSを実行する有効な方法であることを理解しています。私は単にそれが他の方法で行われた場合はどうなるかを尋ねています。
- その場合、結果は異なります。 '申し訳ありませんが、'自分で解決する必要があります。
- @soandos一般的に、複数のDFSトラバーサルになる可能性があります。ここで使用される概念は、 1つの与えられたトラバーサルに関連しており、複数のトラバーサルでは異なります。
回答
無向グラフでのDFSトラバーサルは、頂点に入射するすべてのエッジが探索されるため、クロスエッジを残しません。
ただし、有向グラフでは、エッジに遭遇する場合があります。これは、その頂点が現在の頂点の祖先または子孫ではないように、以前に発見された頂点につながります。このようなエッジはクロスエッジと呼ばれます。
コメント
- アポロフ、ご回答ありがとうございます。ウィキペディアに示されているように、DFSの頂点6に到達すると、6からトラバースする3つのエッジがあるように見えます。その時点で、頂点6は"現在"。最終的には、エッジを頂点3までトラバースします。3はすでにアクセスされていますが、6から3のエッジがあるため、3は" currentの子孫です。 "頂点6。その場合、クロスエッジの定義に違反します。 'が明確にされていない定義には、さらに何かがあるはずです。
- 実際、DFSにはバックエッジのツリーエッジのみが含まれています（はじめにアルゴリズムThm。22.10）。
回答
DFSトラバーサルでは、すべての子が終了するとノードが終了します。終了しました。トラバーサル中に各ノードの検出時間と終了時間をマークすると、開始時間と終了時間を比較して、ノードが子孫であるかどうかを確認できます。実際、DFSトラバーサルは、次のルールに従ってエッジを分割します。
d [node]をノードの検出時間とし、同様にf [node]を終了時間とします。
括弧の定理すべてのu、vについて、次のいずれかが当てはまります。
1。d [u] < f [u] < d [v] < f [ v]またはd [v] < f [v] < d [u] < f [u]であり、uとvのどちらも他方の子孫ではありません。
d [u] < d [v] < f [v] < f [u]およびvはuの子孫です。
d [v] < d [u] < f [u] < f [v]およびuはvの子孫です。
つまり、d [u] < d [v] < f [u] < f [v]は発生しません。
いいね括弧：（）[]、（[]）、および[（）]は問題ありませんが、（[）]および[（]）は問題ありません。
たとえば、エッジのあるグラフについて考えてみます。
A-> B
A-> C
B-> C
訪問の順序を次のように表します。ノードラベルの文字列。「ABCCBA」は、（（（）））と同様に、A-> B-> C（終了）B（終了）A（終了）を意味します。
したがって、「ACCBBA」は「（（）（））」のモデルになる可能性があります。
例：
「CCABBA」：A-> CはクロスですCCがAの内部にないため、エッジ。
“ABCCBA”：A-> Cは前方エッジ（間接的な子孫）です。
“ACCBBA”：A-> Cはツリーエッジです。 （直系の子孫）。
出典：
CLRS：
https://mitpress.mit.edu/books/introduction-algorithms
レクチャーノート http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm