6

ここに画像の説明を入力してください

上記のグラフを考えると、スタックを使用したDFSトラバーサルにより、次のパスが得られます...

1-2-3-4-5-6

上記のパスは有効ですか？別の道はありますか？（私の教科書は私に1-2-3-6-4-5を与えます）

コンピュータサイエンススタックに画像を投稿するのに十分な担当者がいないため、ここで質問する必要がありました。それが適切かどうかはわかりません。そうでない場合は、後で削除できます。

ありがとう、

4

2 に答える 2

6

あなたはグラフの完全に有効なDFSトラバーサルをリストしました、そして教科書はあなたにグラフのもう一つの完全に合法的なDFSトラバーサルを与えています。同じグラフには深さ優先探索が多数存在する可能性があります（実際、指数関数的に多くの探索があります）。したがって、教科書と同じものが得られない場合、それはすぐに警告の原因にはなりません。

その他の注文は次のとおりです。

1 2 5 4 3 6
3 1 6 2 5 4
5 4 2 3 1 6
...

ただし、ノードへのアクセス方法に関する他のルールがある場合（たとえば、接続されているノードを常に昇順または降順でアクセスする場合）、DFS検索では常に同じ出力が生成されます。

お役に立てれば！

于 2012-12-18T19:41:10.603 に答える
1

説明する出力はパスではなく、DFSがノードにアクセスする順序です。パスは、各ノードが前のノードと次のノードに接続されているノードのリストです。

DFSトラバーサルの出力は、DFSトラバーサルツリーとして表示することもできます。これは、次の場合に対応します。

1 - 2 - 3 - 4 - 5
        |
        6

教科書の木は

1 - 2 - 3 - 6 
        |
        4 - 5

選択肢がある各ポイントで最初にどこに行くかを決めることができるので、多くの異なるDFSツリーを取得できます。あなたの例では、ノード3からノード4またはノード6に移動できますが、出力が異なるのは選択が異なるためです。

于 2012-12-19T17:31:41.633 に答える