DFSのエッジ分類

Question

本（アルゴリズムへのイントロ）によると、DFSでは、エッジは4種類に分類されます。

1. ツリーエッジ、エッジ（u、v）で、Vが最初に発見された場合、次に（u、v）はツリーエッジです。
2. バックエッジ、...... vがすでに発見されていて、Vは祖先であり、それはバックエッジです。
3. フォワードエッジ、...... vがすでに発見されており、vはuの子孫であり、前方のエッジです。
4. クロスエッジ、上記の3つを除くすべてのエッジ。

私の質問は、（u、v）が背面または前方のエッジであるかどうかを把握しようとしているときに、vがuの祖先か子孫かをどのように識別できるかです。

Answer 1

本当に必要な場合は、各ノードのいわゆるエントリと退場時間を維持して確認できます。アルゴリズムの実行中、あなたは time 変数（もちろん、0から始まる）新しい頂点に遭遇するたびに。時代 entry_t(v), exit_t(v) 最初はすべての頂点に対して設定されていません。

最初に頂点に遭遇したら、設定します entry(v):=time. 。上端で頂点を出ると（つまり、スタックから頂点を入力します）、その設定 exit(v):=time. 。それで、あなたは持っています

• もしも entry(u) 設定されています exit(u) 設定されていない場合、Uは現在の頂点の祖先です（つまり、Vuはバックエッジです）
• もしも entry(u)>entry(current), 、次に、uは現在の頂点から子孫です（電流 - > uは前方のエッジです）
• そうでなければ、それはクロスエッジです

これらの関係は、アルゴリズムの実行中にチェックするために行われることに注意してください。アルゴリズムが完了した後、祖先のチェックは基本的に

u is_descendant_of v = entry(u)>entry(v) and exit(u)<=exit(v)