Find the level of given node in an Undirected Graph

0 0 6 minutes read

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 -1

An 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 node
int 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 Code
int 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 node
def 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 Code
V=5
edges=[[0,1],[0,2],[1,3],[2,4]]
X=3
 
#Function call
level=findLevel(V,edges,X)
print(level)
 
# This code is contributed by Pushpesh Raj.

C#

// C# code to implement the approach
using 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 node
function 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 Code
let V = 5;
let edges
    = [ [ 0, 1 ], [ 0, 2 ], [ 1, 3 ], [ 2, 4 ] ];
let X = 3;
 
// Function call
let level = findLevel(V, edges, X);
console.log(level);
 
// This code is contributed by ksam24000

Output

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:

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 zambiatek!