广度优先搜索和深度优先搜索

Question

任何人都可以通过它的实现提供一个关于BFS和DFS的简单解释的链接吗？

Answer 1

深度优先搜索:

Answer 2

假设您有以下结构:

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 3

假设你有一棵树如下:

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 4

你可以在wiki上找到所有内容:

BFS和DFS

这个链接也很有用.如果你想要一个实现,请转到:c ++ boost library:DFS