广度优先搜索和深度优先搜索 [英] Breadth First Search and Depth First Search

问题描述

任何人都可以给一个链接，对BFS和DFS一个简单的解释，其执行？

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

推荐答案

可以说，您将得到以下结构：

Lets say you are given the following structure:

Format: Node [Children]

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

探望子女之前，广度优先搜索访问所有节点的孩子。这里的伪code和为上述结构的解决方案：

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

一个深度优先搜索访问树的最低级（最深处的孩子）的第一代替。有两种类型的深度优先搜索的：$ P $对顺序和后序。这只是当你的节点添加到输出（当你访问它VS离开它）之间的区别。

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

这篇关于广度优先搜索和深度优先搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！