19

本 (Intro to Algorithm) によると、dfs では、エッジは 4 種類に分類されます。

  1. ツリー エッジ、エッジ (u,v) で v が最初に検出された場合、(u, v) はツリー エッジです。
  2. バック エッジ、……、v が既に発見されていて、v が先祖である場合、それはバック エッジです。
  3. 前方エッジ、……、v が既に発見されていて、v が u の子孫である場合、前方エッジです。
  4. クロス エッジ、上記 3 つを除くすべてのエッジ。

私の質問は、(u, v) がバック エッジかフォワード エッジかを把握しようとしているときに、v が u の祖先か子孫かをどのように識別できるかということです。

4

1 に答える 1

24

本当に必要な場合は、各ノードのいわゆる開始時間と終了時間を維持することで確認できます。アルゴリズムの実行中は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は現在の頂点の子孫です（current-> uは前方エッジです）
  • それ以外の場合は、クロスエッジです

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

u is_descendant_of v = entry(u)>entry(v) and exit(u)<=exit(v)
于 2011-09-09T13:12:42.187 に答える