...
/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 visitedvisited = [0] * (len(my_graph.graph))# Create a queuequeue = []# Result stringresult = ""# Mark the source node as# visited and enqueue itqueue.append(source)visited[source] = 1while queue:# Dequeue a vertex from queuesource = 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 itwhile my_graph.graph[source] is not None:data = my_graph.graph[source].vertexif visited[data] == 0:queue.append(data)visited[data] = visited[source] + 1my_graph.graph[source] = my_graph.graph[source].next# Counting number of nodes at given levelresult = 0for i in range(len(my_graph.graph)):if visited[i] == level:result += 1return result# Main to test above functionif __name__ == "__main__":V = 5g = 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 ...