2

このdfs/bfsの問題を解決しています。

DFS の反復バージョンと再帰バージョンの両方を作成しました。

ノードにアクセスする順序が異なり、その理由がわかりません。

反復 DFS:

static void DFS (Integer root, Graph graph){

      //  System.out.println("DFS");

        HashSet <Integer> explored = new HashSet<Integer>();
             explored.add(root);

        Stack<Integer> stack = new Stack<Integer>();
              stack.add(root);

        int v; int w;


        while (!stack.isEmpty()){

            v=stack.pop();
            explored.add(v);

            System.out.print(v + " ");
           // for (int i=graph.adjacencies.get(v).size()-1; i>=0; i--) {
            for (int i=0; i < graph.adjacencies.get(v).size(); i++) {
                w = graph.adjacencies.get(v).get(i);

                if (!explored.contains(w)){

                    stack.add(w);
                    explored.add(w);
                }
            }

        }System.out.println();
    }

再帰的 DFS:

static void DFS_2 (Integer root, Graph graph){

//        System.out.println("DFS_2");

        int v; int w;

        v = root;

        graph.explored.add(v);

            System.out.print(v + " ");
            for (int i=0; i < graph.adjacencies.get(v).size(); i++) {

                w = graph.adjacencies.get(v).get(i);

                if (!graph.explored.contains(w)){

                    graph.explored.add(w);
                    DFS_2(w, graph);
                }
            }


    }

チュートリアルの問題では、反復 DFS バージョンでの私の出力は次のとおりです。

1 4 3 2 6

(問題のサンプル出力と再帰バージョンによると):

1 3 2 6 4

ここで何が起こっているのですか？再帰を排除すると、訪問したノードの順序が変更されるのはなぜですか?

-> Netbeans プロジェクトの完全なコード。

4

2 に答える 2

3

を確認graph.adjacencies.get(V)してください。両方のケースで同じ応答が得られますか? その場合、再帰呼び出しとスタック呼び出しでは異なる結果が得られます。たとえば、次のようなツリーです。

      1
    2   3
  4

は、常に左の子を最初に返すと仮定して1->3->2->4、スタック バージョンの順序と再帰バージョンの順序を持​​ちます。1->2->4->3graph.adjacencies.get(V)

于 2012-10-16T12:03:24.113 に答える
1

スタックのため。これはFirst-In、Last-Outであるため、ノードの子をスタックに追加したときとは逆の順序で処理します。

ルートの2人の子供がAとBの順（左から右）であるとします。

最初のアルゴ：

  1. ルートを処理する
  2. スタックにAを追加
  3. スタックにBを追加
  4. スタックからポップします（スタックがFILOであるため、Bになります）

2番目のアルゴ：

  1. ルートを処理する
  2. ハンドルA
  3. ...Aの子供を処理します
  4. ハンドルB

スタックをFIFOであるキュー実装に置き換えることができ、それは問題ないはずです。

于 2011-10-07T15:26:06.720 に答える