Given an undirected graph with V vertices and E edges and a node X, The task is to find the level of node X in the undirected graph. If X does not exist in the graph then return -1.
Note: Traverse the graph starting from vertex 0.
Examples:
Input: V = 5, Edges = {{0, 1}, {0, 2}, {1, 3}, {2, 4}}, X = 3
Output: 2
Explanation: Starting from vertex 0, at level 0 we have node 0, at level 1 we have nodes 1 and 2 and at level 2 we have nodes 3 and 4. So the answer is 2
The example graph
Input: V = 5, Edges = {{0, 1}, {0, 2}, {1, 3}, {2, 4}}, X = 5
Output: -1
Explanation: Vertex 5 is not present in the given graph so answer is -1An example graph
Approach: The problem can be solved based on the following idea:
The given problem can be solved with the help of level order traversal. We can perform a BFS traversal in order to find the level of the given vertex
Follow the steps mentioned below to implement the idea:
- Find the maximum vertex of the graph and store it in a variable (say maxVertex).
- create adjacency list adj[] of size maxVertex+1.
- Check if X is present or not, if not then return -1.
- To traverse the graph, create a queue for level order traversal.
- Push vertex 0 in a queue, and set a counter level to 0.
- Create a visited array of size maxVertex+1 to mark the visited nodes.
- Start BFS traversal if the value of X is found in front of the queue then return the level.
- Keep popping nodes from the queue till it becomes empty and increment the counter level
- In one iteration, push all the unvisited nodes in the queue connected with the current node
- Increment the level variable to jump to the next level.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the level of the given nodeint findLevel(int N, vector<vector<int> >& edges, int X){ // Variable to store maximum vertex of graph int maxVertex = 0; for (auto it : edges) { maxVertex = max({ maxVertex, it[0], it[1] }); } // Creating adjacency list vector<int> adj[maxVertex + 1]; for (int i = 0; i < edges.size(); i++) { adj[edges[i][0]].push_back(edges[i][1]); adj[edges[i][1]].push_back(edges[i][0]); } // If X is not present then return -1 if (X > maxVertex || adj[X].size() == 0) return -1; // Initialize a Queue for BFS traversal queue<int> q; q.push(0); int level = 0; // Visited array to mark the already visited nodes vector<int> visited(maxVertex + 1, 0); visited[0] = 1; // BFS traversal while (!q.empty()) { int sz = q.size(); while (sz--) { auto currentNode = q.front(); q.pop(); if (currentNode == X) { return level; } for (auto it : adj[currentNode]) { if (!visited[it]) { q.push(it); visited[it] = 1; } } } level++; } return -1;}// Driver Codeint main(){ int V = 5; vector<vector<int> > edges = { { 0, 1 }, { 0, 2 }, { 1, 3 }, { 2, 4 } }; int X = 3; // Function call int level = findLevel(V, edges, X); cout << level << endl; return 0;} |
Java
// Java code to implement the approachimport java.util.*;class GFG { // Driver code public static void main(String[] args) { int V = 5; int[][] edges = { { 0, 1 }, { 0, 2 }, { 1, 3 }, { 2, 4 } }; int X = 3; // Function call int level = findLevel(V, edges, X); System.out.println(level); } // Function to find the level of the node public static int findLevel(int N, int[][] edges, int X) { int maxVertex = 0; for (int[] it : edges) { maxVertex = Math.max(maxVertex, Math.max(it[0], it[1])); } // Creating adjacency list ArrayList<Integer>[] adj = new ArrayList[maxVertex + 1]; for (int i = 0; i <= maxVertex; i++) adj[i] = new ArrayList<>(); for (int i = 0; i < edges.length; i++) { adj[edges[i][0]].add(edges[i][1]); adj[edges[i][1]].add(edges[i][0]); } // X is not present if (X > maxVertex || adj[X].size() == 0) return -1; // Queue for BFS traversal LinkedList<Integer> q = new LinkedList<>(); q.offer(0); int level = 0; boolean[] visited = new boolean[maxVertex + 1]; // BFS traversal while (!q.isEmpty()) { int sz = q.size(); while (sz-- > 0) { int currentNode = q.poll(); if (currentNode == X) return level; for (int it : adj[currentNode]) { if (!visited[it]) { q.offer(it); visited[it] = true; } } } level++; } return -1; }} |
Python3
# Python code to implement the approach# Function to find the level of the given nodedef findLevel(N,edges,X): # Variable to store maximum vertex of graph maxVertex=0 for it in edges: maxVertex=max(maxVertex,max(it[0],it[1])) # Creating adjacency list adj=[[] for j in range(maxVertex+1)] for i in range(len(edges)): adj[edges[i][0]].append(edges[i][1]) adj[edges[i][1]].append(edges[i][0]) # If X is not present then return -1 if(X>maxVertex or len(adj[X])==0): return -1 # Initialize a Queue for BFS traversal q=[] q.append(0) level=0 # Visited array to mark the already visited nodes visited=[0]*(maxVertex+1) visited[0]=1 # BFS traversal while(len(q)>0): sz=len(q) while(sz>0): currentNode=q[0] q.pop(0) if(currentNode==X): return level for it in adj[currentNode]: if(not visited[it]): q.append(it) visited[it]=1 sz=sz-1 level=level+1 return -1# Driver CodeV=5edges=[[0,1],[0,2],[1,3],[2,4]]X=3#Function calllevel=findLevel(V,edges,X)print(level)# This code is contributed by Pushpesh Raj. |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;using System.Collections;class GFG { // Function to find the level of the given node static int findLevel(int N, int[, ] edges, int X) { // Variable to store maximum vertex of graph int maxVertex = 0; for (int i = 0; i < edges.GetLength(0); i++) { maxVertex = Math.Max( maxVertex, Math.Max(edges[i, 0], edges[i, 1])); } // Creating adjacency list List<int>[] adj = new List<int>[ maxVertex + 1 ]; for (int i = 0; i <= maxVertex; i++) adj[i] = new List<int>(); for (int i = 0; i < edges.GetLength(0); i++) { adj[edges[i, 0]].Add(edges[i, 1]); adj[edges[i, 1]].Add(edges[i, 0]); } // If X is not present then return -1 if (X > maxVertex || adj[X].Count == 0) return -1; // Initialize a Queue for BFS traversal Queue q = new Queue(); q.Enqueue(0); int level = 0; // Visited array to mark the already visited nodes int[] visited = new int[maxVertex + 1]; for (int i = 0; i <= maxVertex; i++) visited[i] = 0; visited[0] = 1; // BFS traversal while (q.Count != 0) { int sz = q.Count; while (sz-- != 0) { int currentNode = (int)q.Dequeue(); if (currentNode == X) { return level; } for (int i = 0; i < adj[currentNode].Count; i++) { int it = adj[currentNode][i]; if (visited[it] == 0) { q.Enqueue(it); visited[it] = 1; } } } level++; } return -1; } static void Main() { int V = 5; int[, ] edges = new int[, ] { { 0, 1 }, { 0, 2 }, { 1, 3 }, { 2, 4 } }; int X = 3; // Function call int level = findLevel(V, edges, X); Console.Write(level); }}// This code is contributed by garg28harsh. |
Javascript
// JS code to implement the approach// Function to find the level of the given nodefunction findLevel( N, edges, X){ // Variable to store maximum vertex of graph let maxVertex = 0; for (let i=0;i<edges.length;i++){ let it = edges[i]; let a = Math.max(it[0],it[1]); maxVertex = Math.max(maxVertex,a); } // Creating adjacency list let adj = []; for(let i=0;i<maxVertex+1;i++){ adj.push([]); } for (let i = 0; i < edges.length; i++) { adj[edges[i][0]].push(edges[i][1]); adj[edges[i][1]].push(edges[i][0]); } // If X is not present then return -1 if (X > maxVertex || adj[X].length == 0) return -1; // Initialize a Queue for BFS traversal let q = []; q.push(0); let level = 0; // Visited array to mark the already visited nodes let visited = []; for(let i=0;i<maxVertex+1;i++) { visited.push(0); } visited[0] = 1; // BFS traversal while (q.length > 0) { let sz = q.length; while (sz--) { let currentNode = q[0]; q.shift(); if (currentNode == X) { return level; } for(let k =0;k<adj[currentNode].length;k++){ let it = adj[currentNode][k]; if (visited[it]==0) { q.push(it); visited[it] = 1; } } } level++; } return -1;}// Driver Codelet V = 5;let edges = [ [ 0, 1 ], [ 0, 2 ], [ 1, 3 ], [ 2, 4 ] ];let X = 3;// Function calllet level = findLevel(V, edges, X);console.log(level);// This code is contributed by ksam24000 |
Output
2
Time Complexity: O(V + E) For traversing all of the nodes.
Auxiliary Space: O(V) to store all the nodes in the queue.
Related Articles:
- Introduction to Graphs – Data Structure and Algorithm Tutorials
- Breadth First Search or BFS for a Graph
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!