廣度優先搜索和深度優先搜索

Question

任何人可以給出一個鏈接，對BFS和DFS其實現一個簡單的解釋？使用DFS和BFS

Answer 1

比方說，你給出的結構如下：

 
Format: Node [Children] 

A [B C D] 
B [E F] 
C [G] 
D [] 
E [] 
F [] 
G [] 

廣度優先搜索訪問節點的所有孩子的探望子女面前。下面是僞代碼，爲上述結構的解決方案：

 
1. Enqueue root node. 
2. Dequeue and output. If the queue is empty, go to step 5. 
3. Enqueue the dequeued node's children. 
4. Go to Step 2. 
5. Done 

 
Two queues: (Active Node) [Output] [Working Set] 
Starting with root: 
() []    [A] 
(A) [A]    [B C D] 
(B) [A B]   [C D E F] 
(C) [A B C]   [D E F G] 
(D) [A B C D]  [E F G] 
(E) [A B C D E]  [F G] 
(F) [A B C D E F] [G] 
(G) [A B C D E F G] [] 

Done 

深度優先搜索訪問樹的最低水平（最深的孩子），而不是第一次。有兩種類型的深度優先搜索：預購和後訂單。這只是當你將節點添加到輸出時（當你訪問它而離開它時）。

 
    var rootNode = structure.getRoot(); 
    var preOrder = new Array(); 
    var postOrder = new Array(); 
    function DepthFirst(rootNode){ 
     // Pre-order 
     preOrder[ preOrder.length ] = rootNode; 

     for(var child in rootNode){ 
      DepthFirst(child); 
     } 

     // Post-order 
     postOrder[ postOrder.length ] = rootNode; 
    } 

 
Pre-order: 
* A B E F C G D 

Post-order: 
* E F B G C D A 

Answer 2

圖遍歷。

在c++和python。

Answer 3

這裏有幾個鏈接看看：

• Breadth-first search

BFS是不知情的搜索方法，旨在通過擴大和檢查序列的圖形或組合的所有節點系統地搜索每個解決方案。換句話說，它徹底地搜索整個圖或序列，直到找到它爲止。

• Depth-first search

形式上，DFS是不知情的搜索，通過擴大顯示的搜索樹的第一個子節點，因此會越陷越深，直到目標節點進行過程中發現，或者直到它遇到沒有孩子的節點。那麼搜索回溯，回到其還沒有完成探索最新的節點

它們不僅包含它們是如何在應用程序中實現但也有一些算法僞代碼很好的解釋。

Answer 4

假設你有一個樹如下：

alt text http://i40.tinypic.com/289aslh.jpg

它可能是一個有點混亂，因爲E是既是A和F的孩子，但它有助於說明深度優先搜索的深度。深度優先搜索搜索深度較深的樹（因此深度），因爲它可以首先搜索。所以，從左至右遍歷將是A，B，d，F，E，C，G

廣度優先搜索評估所有孩子先着手給孩子的孩子之前。所以同一棵樹會去A，B，C，E，d，F，G

希望這有助於。

Answer 5

​​

Answer 6

你可以找到關於維基一切：

BFS和DFS

這link非常有用了。如果你想實現到：c++ boost library: DFS

Answer 7

深度優先搜索：

Answer 8

繼承人的想法基本知識：

得到一個新的隊列......根節點initalize吧.. ..循環遍歷整個隊列，並不斷從隊列中移除一個項目並將其打印出來（或保存等），並檢查相同的項目是否有任何孩子，如果這樣推他們到隊列中，並繼續在循環中，直到你遍歷整個段（圖）...

Answer 9

與2個指針的片段。

void BFS(int v,struct Node **p) 
{ 
    struct Node *u; 

    visited[v-1] = TRUE; 
    printf("%d\t",v); 
    AddQueue(v); 

    while(IsEmpty() == FALSE) 
    { 
     v = DeleteQueue(); 
     u = *(p+v-1); 

     while(u!=NULL) 
     { 
      if(visited(u->data -1) == FALSE) 
      { 
        AddQueue(u->data); 
        visited[u->data -1]=TRUE; 
        printf("%d\t",u->data); 
      } 

      u = u->next; 
     } 
    } 
} 

Answer 10

BFS和DFS是適用於各種圖形。我只對二進制樹進行解釋。 BFS從上到下訪問每個節點，從左到右。例如，對於這樣的：第一各分支的1個7 9 8 2 3 DFS訪問深度：

 1 
    /\ 
    7 9 
    \/\ 
     8 2 3 

BFS給我們。然後，它回到它的父母身上。你可以遵循這個非正式的規則。首先留下孩子然後右孩子然後父母。但是，你需要從每個分支的深度開始。例如，這裏你從8開始，因爲沒有剩下的孩子爲7，然後你訪問父母7.然後，訪問7的1父母。然後，你去右分支。但是，這一次有2個是最左邊的孩子。那麼，你訪問2（左邊的孩子），然後右邊的孩子3，然後9訪問他們的父母。所以，DFS給了我們8 7 1 2 9 3.這是執行：

import java.util.ArrayList; 
import java.util.List; 

public class TreeTraverse { 

    static class Node{ 
     Node(int data){ 
      this.data = data; 
      this.left = null; 
      this.right = null; 
      this.visited = false; 
     } 
     int data; 
     Node left; 
     Node right; 
     boolean visited; 
    } 

    public static void main(String[] args) { 
     //The tree: 
     // 1 
     ///\ 
     // 7 9 
     // \/\ 
     // 8 2 3 

     Node node1 = new Node(1); 
     Node node7 = new Node(7); 
     Node node9 = new Node(9); 
     Node node8 = new Node(8); 
     Node node2 = new Node(2); 
     Node node3 = new Node(3); 
     node1.left = node7; 
     node1.right = node9; 
     node7.right = node8; 
     node9.right = node3; 
     node9.left = node2; 
     System.out.println("DFS: "); 
     depthFirstSearch(node1); 
     System.out.println("\nBFS: "); 
     breadthFirstSearch(node1); 

    } 

    private static void depthFirstSearch(Node node){ 
     if(node.left == null && node.right == null){ 
      System.out.print(node.data+" "); 
      node.visited = true; 
     }else if(node.left == null || node.left.visited){ 
      depthFirstSearch(node.right); 
      System.out.print(node.data+" "); 
      node.visited = true; 
     }else{ 
      depthFirstSearch(node.left); 
      node.visited = true; 
      System.out.print(node.data+" "); 
      depthFirstSearch(node.right); 

     } 
    } 

    private static void breadthFirstSearch(Node node){ 
     List<Node> al = new ArrayList<>(); 
     al.add(node); 
     while(!al.isEmpty()){ 
      node = al.get(0); 
      if(node.left != null){ 
       int index = al.size(); 
       al.add(index,node.left); 
      } 
      if(node.right != null){ 
       int index = al.size(); 
       al.add(index,node.right); 
      } 
      System.out.print(al.get(0).data+" "); 
      al.remove(0); 


     } 
    } 

} 

我希望它有幫助。如果您想克隆該項目，請訪問：https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java。我希望它有幫助。

Answer 11

首先，BFS和DFS是實現二叉樹遍歷的兩種方式。廣度優先意味着級別遍歷。深度優先有三種實現方式 - ，，。

預購：

a. Start with root, 
b. mark it visited, 
c. go to left node 
d. (b) - mark it visited 
e. Repeat (c) till there is not any new left node remaining 
(We are/might be at leaf node at this point,) 
f. Is there any right node available? If yes, go to (a). 

等級序遍歷 時間複雜度 爲O（n） - 的每個節點被訪問次數爲1只，意味着總的n倍。

空間複雜性 - 最佳案例：樹只剩節點，爲O（1） 平均情況：完美二叉樹例如，n/2個節點，爲O（n）