2 views
in Python

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']

by (26.4k points)

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!