Breadth First Search in C++ – Algorithm and Source Code

Basic Theory

Breadth-first searches are performed by exploring all nodes at a given depth before proceeding to the next level. This means that all immediate children of nodes are explored before any of the children’s children are considered. It has obvious advantage of always finding a minimal path length solution when one exists. However, a great many nodes may need to be explored before a solution is found, especially if the tree is very full.
Algorithm
BFS uses a queue structure to hold all generate but still unexplored nodes. The order in which nodes are placed on the queue for removal and exploration determines the type of search. The BFS algorithm proceeds as follows.

  1. Place the starting node s on the queue.
  2. If the queue is empty, return failure and stop.
  3. If the first element on the queue is a goal node g, return success and stop Otherwise,
  4. Remove and expand the first element from the queue and place all the children at the end of the queue in any order.
  5. Return to step 2.

Example

Consider a graph
BFSGraph

Applying above algorithm, the BFS of the graph starting from node 1 is : 1, 2, 3, 4, 6, 7, 5
Source Code

Complexity

The time complexity of the breadth-first search is O(bd). This can be seen by noting that all nodes up to the goal depth d are generated. Therefore, the number generated is b + b2 + . . . + bd which is O(bd). The space complexity is also O(bd) since all nodes at a given depth must be stored in order to generate the nodes at the next depth, that is, bd-1 nodes must be stored at depth d – 1 to generate nodes at depth d, which gives space complexity of O(bd).
SHARE Breadth First Search in C++ – Algorithm and Source Code

You may also like...

18 Responses

  1. This post seem very yummy!!! I love chocolate!
    Technology, Free Software and Best Tutorial
    your blog is good! I'll visit again 🙂
    God Bless You

  2. Anonymous says:

    In your BFS function, I think you have to remove the 'continue' in the if-statement. Otherwise it's not doing the right thing. Just use for example g.BFS(1, 3); and you will see that the output after the 3rd value is different.

  3. Anonymous says:

    In your bfs program remove that time thing from the void main part..

  4. main function should return an integer value … 🙂

  5. Of course, but my compiler does it for me 🙂 … any way thank you for pointing.

  6. Anonymous says:

    what does this algorithm do exactly?

  7. Anonymous says:

    Got a small memory leak in dequeue. You are leaking temp when you assign front to it.

  8. according to the c++ standard, it is not necessary have a return statement in main()

  9. Wei Song says:

    I think there are memory leak in the queue destructor

  10. Anonymous says:

    Why did you implement your own queue anyway, when there's std::queue?

  11. use of std:queue is recommended.

  12. I sense a memory leak .. no need to allocate memory for the temp variables.

  13. Anonymous says:

    When does the display() function ever get called?

  14. Anonymous says:

    post Output of the program i.e screenshot of ouput

  15. Anonymous says:

    line 156 is added because of the graph is undirected, sure?

  16. Anonymous says:

    Thank a lot.
    The style you code is neat and perspicuous.
    It helps me.

  17. Yes, also it Depend on – if u r using diff Ide such as Code::Blocks

  18. node *p = new node;
    no need of making new node , we just need pointer;
    just write :node *p
    And thank u for code

Leave a Reply

Your email address will not be published. Required fields are marked *

Share