Algorithms for Coding Interviews in C++/

...

/

Solution: Calculate the Number of Nodes in a Given Graph Level

Solution: Calculate the Number of Nodes in a Given Graph Level

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

We'll cover the following...

Solution #1: Iterative Breadth-First Traversal

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

Press + to interact
main.cpp
Graph.cpp
Graph.h
#include "Graph.h"
int Graph::numberOfNodesInGivenLevel(int level) 
{ 
	int source = 0;
	vector <int> visited(this -> vertices, 0); 
	list<int> queue; 
	visited[source] = true; 
	queue.push_back(source); 
	while (!queue.empty()) { 
		source = queue.front(); 
		queue.pop_front(); 
    
		for (auto i = adjacencyList[source].begin(); i != adjacencyList[source].end(); ++i) { 
			if (visited[*i] == 0) { 
				visited[*i] = visited[source] + 1; 
				queue.push_back(*i); 
			} 
		} 
	} 
	int count = 0; 
	for (int i = 0; i < vertices; i++) 
		if (visited[i] == level) 
			count++;	 
	return count; 
}  
 
int main() { 
	Graph g(6);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 3);
  g.addEdge(2, 3);
  g.addEdge(2, 4);
  g.addEdge(3, 5); 
	int level = 1;
	cout << "The number of nodes at level " << level << " are: " << g.numberOfNodesInGivenLevel(level) << endl; 
	level = 2;
	cout << "The number of nodes at level " << level << " are: " << g.numberOfNodesInGivenLevel(level) << endl; 
	level = 3;
	cout << "The number of nodes at level " << level << " are: " << g.numberOfNodesInGivenLevel(level) << endl; 
	return 0; 
}

Psuedocode

Let’s have a look at the pseudocode of modified breadth-first traversal:

Input: root is a node in the graph, level
Output: count of nodes at that level

numberOfNodesInGivenLevel(source, l)
  Let q = queue
  Let level = array //in our code the visited vector
  while source = ø
    print source

    for all adjacent vertices v of source
      q.enqueue(v)
      level[v] = level[v] + 1

    if !q.isEmpty()
      source = q.dequeue()
    else
      source = ø

  //count number of nodes that have level == l

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.

       level[child] = level[parent] + 1.

This is how the level of each node is determined. The root node lies at level zero in the tree.

The highlighted codes show changes in the original BFS algorithm.

Time

...
Access this course and 1400+ top-rated courses and projects.