How to implement Breadth-First-Search non-recursively for a directed graph on python

2
votes

I'm trying to implement a BFS function that will print a list of nodes of a directed graph as visited using Breadth-First-Search traversal. The function has to be implemented non-recursively and it has to traverse through all the nodes in a graph, so if there are multiple trees it will print in the following way:

Tree 1: a, b

Tree 2: d, e, h

Tree 3: .....

My main difficulty is understanding how to make the BFS function traverse through all the nodes if the graph has several trees, without reprinting previously visited nodes.

2
pythonbreadth-first-search

2 Answers

2
votes

For simplicity, you can use a Queue to perform BFS non recursively. You need two data structures here.

  1. A Queue to maintain the BFS order.
  2. List item hash table (or set) to look for duplicates.

This is the algorithm:

  1. Enqueue the initial point on the graph into the queue and also the hash table.
  2. If the queue is not empty
    1. Dequeue from the queue.
    2. Enqueue all neighbors of the dequeued element to the queue and insert them into the set if they are not already present in the set.
    3. Print (/access/process) the dequeued element.
  3. Repeat steps 2 through 4 until the queue is exhausted.

You can find many examples and optimizations online. Eg:

https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/

https://en.wikipedia.org/wiki/Breadth-first_search

0
votes

BFS is usually done with a queue. When you process a node, you push its children onto the queue. After processing the node, you process the next one in the queue.

This is by nature non-recursive.