DFSの探索順序はエッジ分類に影響します

Question

私は大学のDFSとエッジ分類を実装しています（このペーパーで提供されているコードに基づいて：https://courses.csail.mit.edu/6.006/fall11/rec/rec14.pdf）。

私はテストとして、このグラフを使用しました：頂点内部の数字は、それぞれ、発見とファイナライズ時間ある一方でイタリックで

文字は、単に頂点の名前です。エッジは、「戻る」、「進む」、または「クロス」として分類されます。それ以外はツリーのエッジです。

ご覧のとおり、このグラフは次の順序で訪問されました。最初はsです。アクセス可能な隣人がいなくなったとき、訪問はtで始まりました。

私たちのアルゴリズムをテストするために、教師は、各エッジがラインとしてテキストファイルを提供します。 DFSを実行する際には、ファイル内の各頂点の出現順序に従います。この場合には、それはs、その後v、ないt最初のだろう。これは、順番に異なるエッジの分類を与える：ttツリー1 バック1とuからuからvクロスエッジとみなされ、tに。

この動作は正常ですか？探索の順序は最終的なエッジ分類に影響するか？もしそうなら、両方の分類、私の例、正しいのでしょうか？そうでない場合は、最初にどの頂点を探索するかわかりますか？

Answer 1

この動作は正常ですか？探索の順序は最終的なエッジ分類に影響するか？

絶対に。任意バックまたはクロスエッジがある場合、アルゴリズムは、探査のためのエッジを選択する順序は、ケースのエッジの分類を決定する（すなわち、グラフは、ない木。ある場合）

そうであれば、両方の分類であり、鉱山そしてその例は正しい？

はい、両方の分類は、問題設定ツールによって要求された特定の探索順序がない限り正確です。

もしそうでない場合は、最初にどの頂点を探索するか知る方法はありますか？

探査の特定の順序を指定することができ、問題が

- 例えば、あなたの写真上のグラフは頂点命名の逆のアルファベット順に横断するように表示されます。zからw前s、yからw前z、そしてv より前のuより前。