...

/

Solution: Calculate the Number of Nodes in a Graph Level

Solution: Calculate the Number of Nodes in a Graph Level

This review provides a detailed analysis of the different ways to calculate the number of nodes in a graph at a given level.

We'll cover the following...

Solution:

def number_of_nodes(my_graph, level):
"""
Calculates the number of nodes at given level
:param graph: The graph
:return: Total number of nodes at given level
"""
source = 0
# Mark all the vertices as not visited
visited = [0] * (len(my_graph.graph))
# Create a queue
queue = []
# Result string
result = ""
# Mark the source node as
# visited and enqueue it
queue.append(source)
visited[source] = 1
while queue:
# Dequeue a vertex from queue
source = queue.pop(0)
# Get all adjacent vertices of the
# dequeued vertex source. If a adjacent
# has not been visited, then mark it
# visited and enqueue it
while my_graph.graph[source] is not None:
data = my_graph.graph[source].vertex
if visited[data] == 0:
queue.append(data)
visited[data] = visited[source] + 1
my_graph.graph[source] = my_graph.graph[source].next
# Counting number of nodes at given level
result = 0
for i in range(len(my_graph.graph)):
if visited[i] == level:
result += 1
return result
# Main to test above function
if __name__ == "__main__":
V = 5
g = Graph(V)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
print(number_of_nodes(g, 2))

Explanation

The solution above modifies the visited list to store the level of each node. Later, count the nodes with the same level.

In this code, while visiting each node, the level of that node is set with an increment in the level of its parent node, i.e.,

       visited[child] = visited[parent] + 1 

This is how the level of each node is determined.

Time complexity

Its time complexity is the same as the breadth-first traversal algorithm. We have added no new loops, just a simple list to do our job.

The time complexity of BFS can be computed as the total number of iterations performed by the loop.

Let EE ...