Python Implement Breadth-First Search

Question

I found a model on the web, nonetheless, returning just the sequence of the BFS components isn't sufficient for computation. Suppose the root is the main degree(first level) of the BFS tree, at that point its children are the second level, and so forth How might I realize which level would they say they are in, and who is the parent of every node from the code beneath (I will make 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']

Answer 1

You can monitor the degrees of every node by first assigning level 0 to the beginning node. At that point for each adjacent node X relegate level level_of_X + 1. 

Additionally, your code pushes a similar node on numerous occasions into the queue. I utilized a different list visited to stay away from 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)

Are you interested to learn the concepts of python? Join the python training course fast!