7

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']
Improve this question
3
  • this post belongs to codereview site Commented Apr 11, 2018 at 19:04
  • 1
    @AmiNadimi Unfortunately, it doesn't belong to Code Review. It asks for new features (mainly the nodes' predecessors in the traversal). Asking for new features is off-topic on Code Review. See our guide for Stack Overflow users for more information. Commented Apr 11, 2018 at 19:07
  • ideally explored should be a set(), otherwise this is potentially O(N*N). Also queue should be a dequeue for faster pop(0) Commented Apr 20, 2019 at 19:15

2 Answers 2

Reset to default
9

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)
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

is it possible to also find their parent?
I have found their parent, thanks a lot. But it is better to use deque, however, my node in graph may be integer that deque is not allowed to do so. Do you know how to fix this?
pop(0) removes the first element of the array. So it is being used as a queue.
@user5575144: Not sure what deque can't do that you'd need. It can hold any object. You can't index it, but you shouldn't need to index queue here. However, queue would work just as well as a stack by using pop() instead of pop(0)
what's the advantage of queue over recursive call(if possible, could you add recursive version?)?
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.

Improve this answer

3 Comments

However, pop is being used, so it's O(1). It's actually a stack, not a queue.
When you pass an index to pop, it pops the element at that index. In this case, since the index 0 is being passed, it will remove the first element of the list. So the list is being used like a queue.
Oops! Right: pop(0) does make it q queue, but a very inefficient queue, since pop(0) is O(N) as you pointed out. Better to use a deque, or just use a list as a stack (using pop()) which would work just as well here. If the neighbors aren't sorted to begin with, there's no significant difference.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.