Data Modelling & AI Data Structure & Algorithm

Print Nodes after level K from given node in Graph in ascending order

28 July 2024

1

Given an undirected graph, a source node src, and an integer K, the task is to print all nodes after level K from the source node in ascending order
(nodes are from 1 to N ).

Examples:

Input: { (1, 2), (1, 3), (1, 4), (1, 5), (2, 10), (2, 4), (3, 8), (3, 9), (4, 11), (5, 6), (5, 7), (8, 12), (10, 13) }, K = 1, src = 1
Output: 6 7 8 9 10 11 12 13

under level 1 – 1, 2, 3, 4, 5

Input 2: {, (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9) }, K = 2, src = 4
Output: 1 7 8 9

under level 2 : 2, 3, 4, 5, 6

Approach: This can be solved with the following idea:

Using BFS, while moving across the neighboring element of src and maintaining levels in order to keep a count that we have crossed K. Once, K is crossed push the nodes data into a vector which will be returned as output.

Steps involved in the implementation of the above approach:

Make an adjacency list from the input.
Take a vector ans to store all nodes after level K.
Take a queue for BFS traversal.
When we iterate the queue for more than K times it means that now nodes present in the queue lie after level K.
Take a visited array to check whether the particular node is previously visited or not.
Take a top element of the queue and rest on that node and add every neighbor node of that particular node into the queue.
At last sort the ans array and print all elements.

Below is the code for the implementation of the above approach:

C++

// C++ code for above approach
#include <bits/stdc++.h>
using namespace std;
 
vector<int> afterLevelK(int src, int k, vector<int> adj[],
                        int n)
{
 
    // Create a visited array to check the
    // particular node is previously
    // visited or not
    vector<int> vis(n + 1, 0);
 
    // Take queue for BFS traversal
    queue<int> q;
 
    // Ans vector to store all element
    // lies after level k
    vector<int> ans;
 
    // Push src node into queue and
    // mark it as visited
    q.push(src);
    vis[src] = 1;
 
    // Traverse graph
    while (!q.empty()) {
        int n = q.size();
        while (n--) {
 
            // Take top element of queue
            // and pop it
            int top = q.front();
            q.pop();
 
            // If element lies after level
            // k then push it in ans vector
            if (k < 0) {
                ans.push_back(top);
            }
 
            // Rest on node and check
            // its neighbour nodes
            for (auto x : adj[top]) {
 
                // If adjacent node is
                // not visited then mark
                // it as visited and
                // push it into queue
                if (!vis[x]) {
                    q.push(x);
                    vis[x] = 1;
                }
            }
        }
 
        // Decrement the level
        k--;
    }
 
    return ans;
}
 
// Drivers code
int main()
{
 
    // Total number of nodes
    int n = 9;
 
    // All links in undirected graph
    vector<pair<int, int> > links
        = { { 1, 2 }, { 2, 3 }, { 3, 4 }, { 4, 5 },
            { 5, 6 }, { 6, 7 }, { 7, 8 }, { 8, 9 } };
 
    // Adjacency list
    vector<int> adj[n + 1];
 
    // Create graph in form of
    // adjacency list
    for (auto it : links) {
        int u = it.first;
        int v = it.second;
 
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    // Source node
    int src = 4;
 
    // Level
    int k = 2;
 
    // Function call
    vector<int> ans = afterLevelK(src, k, adj, n);
 
    // sort ans vector
    sort(ans.begin(), ans.end());
 
    // Traverse and print ans vector
    for (auto it : ans) {
        cout << it << " ";
    }
 
    return 0;
}

Java

// Java code for above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    static List<Integer>
    afterLevelK(int src, int k, ArrayList<Integer>[] adj,
                int n)
    {
 
        // Create a visited array to check whether the
        // particular node is previously visited or not
        boolean[] vis = new boolean[n + 1];
 
        // Take a queue for BFS traversal
        Queue<Integer> q = new LinkedList<>();
 
        // Ans list to store all elements lies after level k
        List<Integer> ans = new ArrayList<>();
 
        // Push src node into queue and mark it as visited
        q.offer(src);
        vis[src] = true;
 
        // Traverse graph
        while (!q.isEmpty()) {
            int len = q.size();
            while (len-- > 0) {
 
                // Take top element of queue and poll it
                int top = q.poll();
 
                // If element lies after level k then add it
                // in ans list
                if (k < 0) {
                    ans.add(top);
                }
 
                // Rest on node and check its neighbor nodes
                for (int x : adj[top]) {
 
                    // If adjacent node is not visited then
                    // mark it as visited and add it into
                    // queue
                    if (vis[x] == false) {
                        q.add(x);
                        vis[x] = true;
                    }
                }
            }
 
            // Decrement the level
            k--;
        }
 
        return ans;
    }
 
    public static void main(String[] args)
    {
        // Total number of nodes
        int n = 9;
 
        // All links in undirected graph
        int[][] links
            = { { 1, 2 }, { 2, 3 }, { 3, 4 }, { 4, 5 },
                { 5, 6 }, { 6, 7 }, { 7, 8 }, { 8, 9 } };
 
        // Adjacency list
        ArrayList<Integer>[] adj = new ArrayList[n + 1];
 
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
 
        // create graph in form of adjaceny list
        for (int[] link : links) {
            int u = link[0];
            int v = link[1];
 
            adj[u].add(v);
            adj[v].add(u);
        }
 
        // source node
        int src = 4;
 
        // level
        int k = 2;
 
        // Function call
        List<Integer> ans = afterLevelK(src, k, adj, n);
 
        // sort the ans arraylist
        Collections.sort(ans);
 
        // traverse and print ans vector
        for (int it : ans) {
            System.out.print(it + " ");
        }
    }
}
 
// This code is contributed by lokesh.

Python3

from collections import deque
 
 
def after_level_k(src, k, adj, n):
    # Create a visited array to check if the
    # particular node is previously visited or not
    vis = [False] * (n + 1)
 
    # Take a queue for BFS traversal
    q = deque()
 
    # Ans list to store all elements
    # that lie after level k
    ans = []
 
    # Push src node into queue and
    # mark it as visited
    q.append(src)
    vis[src] = True
 
    # Traverse graph
    while q:
        n = len(q)
        while n > 0:
            # Take the top element of queue
            # and pop it
            top = q.popleft()
 
            # If element lies after level k
            # then append it to ans list
            if k < 0:
                ans.append(top)
 
            # Rest on node and check
            # its neighbour nodes
            for x in adj[top]:
                # If adjacent node is not visited
                # then mark it as visited and
                # append it to queue
                if not vis[x]:
                    q.append(x)
                    vis[x] = True
 
            n -= 1
 
        # Decrement the level
        k -= 1
 
    return ans
 
 
# Driver code
if __name__ == "__main__":
    # Total number of nodes
    n = 9
 
    # All links in undirected graph
    links = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)]
 
    # Adjacency list
    adj = [[] for _ in range(n+1)]
 
    # Create graph in form of adjacency list
    for u, v in links:
        adj[u].append(v)
        adj[v].append(u)
 
    # Source node
    src = 4
 
    # Level
    k = 2
 
    # Function call
    ans = after_level_k(src, k, adj, n)
 
    # Sort ans list
    ans.sort()
 
    # Traverse and print ans list
    for it in ans:
        print(it, end=" ")

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
class Program {
    static List<int> AfterLevelK(int src, int k,
                                 List<int>[] adj, int n)
    {
        // Create a visited array to check if
        // a particular node is previously visited or not
        bool[] vis = new bool[n + 1];
 
        // Take queue for BFS traversal
        Queue<int> q = new Queue<int>();
 
        // Ans list to store all elements
        // that lie after level k
        List<int> ans = new List<int>();
 
        // Push src node into queue and mark it as visited
        q.Enqueue(src);
        vis[src] = true;
 
        // Traverse graph
        while (q.Count > 0) {
            int count = q.Count;
            while (count-- > 0) {
                // Take top element of queue and dequeue it
                int top = q.Dequeue();
 
                // If element lies after level k, then add
                // it to ans list
                if (k < 0) {
                    ans.Add(top);
                }
 
                // Visit adjacent nodes and push them into
                // queue if not visited
                foreach(int x in adj[top])
                {
                    if (!vis[x]) {
                        q.Enqueue(x);
                        vis[x] = true;
                    }
                }
            }
 
            // Decrement the level
            k--;
        }
 
        return ans;
    }
 
    static void Main(string[] args)
    {
        // Total number of nodes
        int n = 9;
 
        // All links in undirected graph
        Tuple<int, int>[] links = new Tuple<int, int>[] {
            Tuple.Create(1, 2), Tuple.Create(2, 3),
            Tuple.Create(3, 4), Tuple.Create(4, 5),
            Tuple.Create(5, 6), Tuple.Create(6, 7),
            Tuple.Create(7, 8), Tuple.Create(8, 9)
        };
 
        // Adjacency list
        List<int>[] adj = new List<int>[ n + 1 ];
        for (int i = 0; i <= n; i++) {
            adj[i] = new List<int>();
        }
 
        // Create graph in form of adjacency list
        foreach(Tuple<int, int> it in links)
        {
            int u = it.Item1;
            int v = it.Item2;
 
            adj[u].Add(v);
            adj[v].Add(u);
        }
 
        // Source node
        int src = 4;
 
        // Level
        int k = 2;
 
        // Function call
        List<int> ans = AfterLevelK(src, k, adj, n);
 
        // Sort ans list
        ans.Sort();
 
        // Traverse and print ans list
        foreach(int it in ans) { Console.Write(it + " "); }
    }
}

Javascript

function afterLevelK(src, k, adj, n) {
    // Create a visited array to check whether
    // a particular node is previously visited or not
    const vis = new Array(n + 1).fill(0);
 
    // Take a queue for BFS traversal
    const q = [];
 
    // Ans array to store all elements
    // that lie after level k
    const ans = [];
 
    // Push the src node into the queue and
    // mark it as visited
    q.push(src);
    vis[src] = 1;
 
    // Traverse the graph
    while (q.length !== 0) {
        const levelSize = q.length;
 
        for (let i = 0; i < levelSize; i++) {
            // Take the top element of the queue
            // and remove it from the queue
            const top = q.shift();
 
            // If the element lies after level k,
            // then push it into the ans array
            if (k < 0) {
                ans.push(top);
            }
 
            // Explore the neighbours of the current node
            for (let j = 0; j < adj[top].length; j++) {
                const neighbour = adj[top][j];
 
                // If the adjacent node is not visited,
                // then mark it as visited and push it into the queue
                if (!vis[neighbour]) {
                    q.push(neighbour);
                    vis[neighbour] = 1;
                }
            }
        }
 
        // Decrement the level
        k--;
    }
 
    return ans;
}
 
// Driver code
(function main() {
    // Total number of nodes
    const n = 9;
 
    // All links in undirected graph
    const links = [
        [1, 2],
        [2, 3],
        [3, 4],
        [4, 5],
        [5, 6],
        [6, 7],
        [7, 8],
        [8, 9]
    ];
 
    // Adjacency list
    const adj = new Array(n + 1).fill().map(() => []);
 
    // Create the graph in the form of
    // an adjacency list
    for (const [u, v] of links) {
        adj[u].push(v);
        adj[v].push(u);
    }
 
    // Source node
    const src = 4;
 
    // Level
    const k = 2;
 
    // Function call
    const ans = afterLevelK(src, k, adj, n);
 
    // Sort ans array
    ans.sort((a, b) => a - b);
 
    // Traverse and print ans array
    console.log(ans.join(' '));
})();

Output

1 7 8 9

Time Complexity: O (V+E)
Auxiliary Space: O (V)

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!

Commit to GfG’s Three-90 Challenge! Purchase a course, complete 90% in 90 days, and save 90% cost click here to explore.

Last Updated :
20 Apr, 2023

Previous

<!–

8 Min Read | Java

–>

Querying frequency of elements in a range

Next

<!–

8 Min Read | Java

–>

What is Binary Search Algorithm?

Share your thoughts in the comments

Print Nodes after level K from given node in Graph in ascending order

C++

Java

Python3

C#

Javascript

Run Local AWS Cloud Stack using LocalStack on Linux

Learn Terraform Automation in 3 days using Video Courses

How To Expose Ansible AWX Service using Nginx Ingress

LEAVE A REPLY Cancel reply

Most Popular

Vietnam’s Success in Software Outsourcing

Install Python 3 / Python 2.7 on Rocky Linux 8 |AlmaLinux 8

How To Manage Angular JS Projects using Angular CLI

How To Install PHP 8.2 on Ubuntu 22.04|20.04|18.04

Recent Comments

EDITOR PICKS

Vietnam’s Success in Software Outsourcing

Install Python 3 / Python 2.7 on Rocky Linux 8 |AlmaLinux 8

How To Manage Angular JS Projects using Angular CLI

POPULAR POSTS

Vietnam’s Success in Software Outsourcing

Install Python 3 / Python 2.7 on Rocky Linux 8 |AlmaLinux 8

How To Manage Angular JS Projects using Angular CLI

POPULAR CATEGORY

ABOUT US

FOLLOW US

Print Nodes after level K from given node in Graph in ascending order

C++

Java

Python3

C#

Javascript

Please Login to comment…

LEAVE A REPLY Cancel reply

Most Popular

Recent Comments

EDITOR PICKS

POPULAR POSTS

POPULAR CATEGORY

ABOUT US

FOLLOW US