广度优先搜索，深度优先搜索

Can anybody give a link for a simple explanation on BFS and DFS with its implementation?

有没有人可以提供一个关于BFS和DFS实现的简单解释的链接?

11 个解决方案

#1

Lets say you are given the following structure:

假设你有以下结构:

Format: Node [Children]

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

A breadth first search visits all of a node's children before visiting their children. Here's the pseudocode and the solution for the above structure:

广度优先搜索在访问节点的子节点之前访问节点的所有子节点。下面是伪代码和上述结构的解决方案:

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

A depth first search visits the lowest level (deepest children) of the tree first instead. There are two types of depth first search: pre-order and post-order. This just differentiates between when you add the node to the output (when you visit it vs leave it).

深度搜索首先访问树的最低层(最深的子层)。有两种类型的深度优先搜索:前序和后序。这与将节点添加到输出(当您访问它时与退出它时)是不同的。

    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

#2

Depth First Search:

深度优先搜索:

#3

Say you have a tree as follows:

假设你有这样一棵树:

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

alt文本http://i40.tinypic.com/289aslh.jpg

It may be a little confusing because E is both a child of A and F but it helps illustrate the depth in a depth first search. A depth first search searches the tree going as deep (hence the term depth) as it can first. So the traversal left to right would be A, B, D, F, E, C, G.

这可能有点让人困惑，因为E是a和F的子元素，但它有助于在深度优先搜索中说明深度。深度搜索首先搜索树的深度(也就是深度)。所以从左到右的遍历是A B D F E C G。

A breadth first search evaluates all the children first before proceeding to the children of the children. So the same tree would go A, B, C, E, D, F, G.

广度先研究所有的孩子，然后再研究孩子的孩子。所以同样的树会有A B C E D F G。

Hope this helps.

希望这个有帮助。

#4

you can find everything on wiki:

你可以在维基上找到所有的东西:

BFS and DFS

BFS和DFS

this link can be useful too. if you want an implementation go to: c++ boost library: DFS

这个链接也很有用。如果希望实现，请转到:c++ boost库:DFS

#5

Here are a few links to check out:

这里有几个链接可以查看:

• Breadth-first search
• 广度优先搜索

BFS is an uninformed search method that aims to expand and examine all nodes of a graph or combination of sequences by systematically searching through every solution. In other words, it exhaustively searches the entire graph or sequence without considering the goal until it finds it.

BFS是一种不知情的搜索方法，它通过系统地搜索每个解决方案来扩展和检查图的所有节点或序列的组合。换句话说，它会搜索整个图或序列，而不会考虑目标，直到找到目标为止。

• Depth-first search
• 深度优先搜索

Formally, DFS is an uninformed search that progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal node is found, or until it hits a node that has no children. Then the search backtracks, returning to the most recent node it hasn't finished exploring

正式地说，DFS是一种不知情的搜索，它通过扩展出现的搜索树的第一个子节点，从而不断深入，直到找到目标节点，或者直到找到没有子节点为止。然后搜索返回，返回到它尚未完成搜索的最新节点

Not only do they contain good explanations on how they are implemented in applications but also some algorithm pseudo code.

它们不仅包含了如何在应用程序中实现它们的良好解释，而且还包含一些算法伪代码。

#6

Breadth First Search/Depth First Search Animations

广度优先搜索/深度优先搜索动画。

#7

graph traversal with dfs and bfs.

使用dfs和bfs进行图形遍历。

in c++ and python.

在c++和python。

#8

Heres the idea in basics:

这里有一个基本的想法:

get a new queue ...initalize it with the root node .... loop through the entire queue and keep removing an item from the queue and printing it out (or saving it etc) and check if the same item has any children , if so push them onto the queue and continue in the loop until you traverse the entire segment(graph)...

找一个新的队列……与根节点.... initalize循环遍历整个队列，并从队列中删除一个项，并将其打印出来(或保存它等)，并检查同一项是否有任何子元素，如果将它们推到队列上，并在循环中继续，直到遍历整个段(图)……

#9

snippet with 2 pointers.

片段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;
         }
     }
}

#10

BFS and DFS are applicable to all kinds of graphs. I explain it for binary tree only. BFS visit each node top to bottom, left to right. For example for this:

BFS和DFS适用于各种图形。我只对二叉树进行解释。BFS访问每个节点从上到下，从左到右。例如:

       1
      / \
     7   9
     \  / \
      8 2 3

BFS gives us: 1 7 9 8 2 3. DFS visits depth of each branch first. Then, it comes back to its parents. You can follow this informal rule. First left child then right child then parent. But, you need to start from the depth of each branch. For example, here you start from 8, since there is no left child for 7. Then, you visit parent 7. Then, 1 parent of 7 will be visited. Then, you go to right branch. But, this time there is 2 as the left most child. So, you visit 2 (left child) then, right child 3 then, 9 their parents. So, DFS gives us 8 7 1 2 9 3. This is the implementation:

BFS得到:1 7 9 8 2 3。DFS首先访问每个分支的深度。然后，它又回到了它的父母身上。你可以遵循这个非正式的规则。首先是左子，然后是右子，然后是父。但是，您需要从每个分支的深度开始。例如，这里从8开始，因为7没有左子结点。然后，你去看望父母7。然后，将访问7个父节点。然后，你到右分支。但是，这一次有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);


        }
    }

}

I hope it helps. If you want to clone the project, please visit: https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java. I hope it helps.

我希望它有帮助。如果您想克隆这个项目，请访问:https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java。我希望它有帮助。

#11

First of all, BFS and DFS are two ways to implement binary tree traversal. Breadth First means level order traversal. Depth First has three ways to implemnt -- , , .

首先，BFS和DFS是实现二叉树遍历的两种方法。宽度首先是水平顺序遍历。Depth首先有三种实现方法——。

Preorder:

预订:

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).

Level Order Traversal Time Complexity O(n)- Number of times each node is visited is 1 only, means total is n times.

层序遍历时间复杂度O(n)——每个节点访问次数为1次，表示总次数为n次。

Space Complexity- Best Case: Tree only left nodes, is O(1) Average Case: Perfect binary tree is example, n/2 number of nodes, O(n)

空间复杂度-最佳情况:树仅左节点，是O(1)平均情况:完美的二叉树为例，n/2节点个数，O(n)