Breadth First Search and Depth First Search

Question

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

Answer 1

graph traversal with dfs and bfs.

in c++ and python.

Answer 2

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.

• 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

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

Answer 3

Say you have a tree as follows:

It may be a little confusing because E is both a child of A and F but it helps illustrate the dpeth-ness of 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 would go 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.

Hope this helps.

Answer 4

Breadth First Search/Depth First Search Animations

Answer 5

you can find everything on wiki:

BFS and DFS

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

Answer 6

Lets say you are given the following structure:

Format: Node [Children]

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

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

Answer 7

Depth First Search: