Python Implement Breadth-First Search

Question

I found an example online, however, returning only the sequence of the BFS elements is not enough for calculation. Let's say the root is the first level of the BFS tree, then its children are second level, etc. How can I know which level are they in, and who is the parent of each node from the code below (I will create an object to store its parent and tree level)?

# sample graph implemented as a dictionary
graph = {'A': ['B', 'C', 'E'],
         'B': ['A','D', 'E'],
         'C': ['A', 'F', 'G'],
         'D': ['B'],
         'E': ['A', 'B','D'],
         'F': ['C'],
         'G': ['C']}

# visits all the nodes of a graph (connected component) using BFS
def bfs_connected_component(graph, start):
   # keep track of all visited nodes
   explored = []
   # keep track of nodes to be checked
   queue = [start]

   # keep looping until there are nodes still to be checked
   while queue:
       # pop shallowest node (first node) from queue
       node = queue.pop(0)
       if node not in explored:
           # add node to list of checked nodes
           explored.append(node)
           neighbours = graph[node]

           # add neighbours of node to queue
           for neighbour in neighbours:
               queue.append(neighbour)
   return explored

bfs_connected_component(graph,'A') # returns ['A', 'B', 'C', 'E', 'D', 'F', 'G']

Solution 1

You can keep track of the levels of each node by first assigning level 0 to the start node. Then for each neighbor of node X assign level level_of_X + 1.

Also, your code pushes the same node multiple times into the queue. I used a separate list visited to avoid that.

# sample graph implemented as a dictionary
graph = {'A': ['B', 'C', 'E'],
         'B': ['A','D', 'E'],
         'C': ['A', 'F', 'G'],
         'D': ['B'],
         'E': ['A', 'B','D'],
         'F': ['C'],
         'G': ['C']}


# visits all the nodes of a graph (connected component) using BFS
def bfs_connected_component(graph, start):
    # keep track of all visited nodes
    explored = []
    # keep track of nodes to be checked
    queue = [start]

    levels = {}         # this dict keeps track of levels
    levels[start]= 0    # depth of start node is 0

    visited= [start]     # to avoid inserting the same node twice into the queue

    # keep looping until there are nodes still to be checked
    while queue:
       # pop shallowest node (first node) from queue
        node = queue.pop(0)
        explored.append(node)
        neighbours = graph[node]

        # add neighbours of node to queue
        for neighbour in neighbours:
            if neighbour not in visited:
                queue.append(neighbour)
                visited.append(neighbour)

                levels[neighbour]= levels[node]+1
                # print(neighbour, ">>", levels[neighbour])

    print(levels)

    return explored

ans = bfs_connected_component(graph,'A') # returns ['A', 'B', 'C', 'E', 'D', 'F', 'G']
print(ans)

Solution 2

Yeah, this code only visits the nodes in a breadth-first fashion. This by itself is a useful thing to do for many applications (for example finding shortest paths in an unweighted graph)

To actually return the BFS tree would require some additional work. You can think about either storing a list of children for each node, or returning pairs of (node, parent-node). Either representation should allow you to figure out the structure of the tree.

Another thing to note here, is that the code uses python lists as a queue, which is not a good idea. Because removing the first element from a list, requires O(n) time.