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 approachÂ
import 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!
