16

幅優先探索のJavaコードは次のとおりです。

void breadthFirstNonRecursive(){
    Queue<Node> queue = new java.util.LinkedList<Node>();
    queue.offer(root);
    while(!queue.isEmpty()){
        Node node = queue.poll();
        visit(node);
        if (node.left != null)
            queue.offer(node.left);
        if (node.right != null)
            queue.offer(node.right);
    }
}

同じことをする再帰関数を書くことは可能ですか？

最初は、これは簡単だと思ったので、次のように思いつきました。

void breadthFirstRecursive(){
    Queue<Node> q = new LinkedList<Node>();
    breadthFirst(root, q);
}

void breadthFirst(Node node, Queue<Node> q){
    if (node == null) return;
    q.offer(node);
    Node n = q.poll();
    visit(n);
    if (n.left != null)
        breadthFirst(n.left, q);
    if (n.right != null)
        breadthFirst(n.right, q);   
}

それから私はそれが機能しないことに気づきました。それは実際にはこれと同じことをします：

void preOrder(Node node) {
    if (node == null) return;
    visit(node);
    preOrder(node.left);
    preOrder(node.right);
}

これについて誰かが以前に考えたことがありますか？

4

6 に答える 6

21

完全に優れた反復ソリューションがあるのに、なぜそうしたいのか想像できませんが、ここに行きます;）

void breadth_first(Node root):
  Queue q;
  q.push(root);
  breadth_first_recursive(q)

void breadth_first_recursive(Queue q):
  if q.empty() return;

  Node n = q.pop()
  print "Node: ", n
  if (n.left) q.push(n.left)
  if (n.right) q.push(n.right)
  breadth_first_recursive(q)

ツリーのノードを本当に再帰的にトラバースしたい場合は、levelパラメーターを使用してDFSを実行し、でのみノードを出力してlevelから、再帰することを追加する必要があります。しかし、それはクレイジーな話です。ノードを何度も再訪するからです...BFSが反復アルゴリズムであることを受け入れてください。:)

于 2010-06-03T19:23:14.763 に答える
12

BFSアルゴリズムは、（DFSとは対照的に）再帰的アルゴリズムではありません。

アルゴリズムをエミュレートする再帰関数を書いてみることができますが、それはかなり奇妙な結果になります。これを行うことのポイントは何でしょうか？

于 2010-06-03T19:23:19.677 に答える
9

反復深化深さ優先探索を使用できます。これは、再帰を使用する幅優先アルゴリズムです。分岐係数が高い場合は、メモリをあまり使用しないため、BFSよりも優れています。

于 2010-06-03T19:58:13.647 に答える
1

単純なBFSおよびDFS再帰：スタック/キュー内のツリーのルートノードをプッシュ/オファーして、これらの関数を呼び出すだけです！

public void breadthFirstSearch(Queue queue) {
if (queue.isEmpty()) 
  return;

Node node = (Node) queue.poll();

System.out.println(node + " ");

if (node.right != null) 
  queue.offer(node.right);

if (node.left != null) 
  queue.offer(node.left);

breadthFirstSearch(queue);

}

public void depthFirstSearch(Stack stack) {
if (stack.isEmpty()) 
  return;

Node node = (Node) stack.pop();

System.out.println(node + " ");

if (node.right != null) 
  stack.push(node.right);

if (node.left != null) 
  stack.push(node.left);

depthFirstSearch(stack);

}

于 2015-05-04T01:21:23.890 に答える
1

これは、キューの代わりにarraylistを使用した例です。隣接行列と、訪問した配列を事前定義しました。エッジも作成しました


    public void BFS(int node, boolean[]visited)
        {
         List<Integer> li=new ArrayList<>();
         for(int j:adj[node])
         {
           if(!visited[j])
             {
                 System.out.println(j+" ");
                 visited[j]=true;
                 li.add(j);
             }
         }
             for(int j:li){
                 BFS(j,visited);
             }
        }
于 2021-10-15T01:05:22.580 に答える
0

これはすべての人を満足させるものではありません-私は確信しています。みんなに敬意を表して。ポイントは何ですか？重要なのは、すべての反復アルゴリズムには（簡単な？）再帰的なソリューションもあると信じているということです。これがstackoverflowからの「sisis」による解決策です。

BFS(Q)

{

  if (|Q| > 0) 

     v < - Dequeue(Q)

     Traverse(v)
     foreach w in children(v)
        Enqueue(Q, w)    

     BFS(Q)
}

ある程度おかしなものが含まれていますが、再帰的なルールに違反していることは明らかではありません。再帰的なルールに違反していない場合は、受け入れる必要があります。私見では。

于 2013-02-26T21:03:40.127 に答える