Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Terms to Define✨
3.
Problem Statement🕵️‍♂️
3.1.
Example
4.
Approach👩‍💻
5.
Solution
5.1.
💥Complexities
6.
Frequently Asked Questions
6.1.
What is Graph?
6.2.
Why are graphs important data structures?
6.3.
What does a reachable node mean?
6.4.
What is the time complexity to find all reachable nodes from every node present in a given set?
6.5.
What is BFS traversal?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Find all Reachable Nodes from Every Node Present in a Given Set

Author yuvatimankar
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will design an algorithm to find all reachable nodes from every node in a given set. But, before this, we will see some terms such as graph, node, etc.

Find all reachable nodes from every node present in a Given set

Now, Let's get Started with the topics!

Terms to Define✨

Graph A graph data structure is a non-linear data structure that contains two non-empty sets of vertices and edges. 
Node It is defined as one of the points on which a graph is defined.
Reachable Node When two nodes are connected directly, they are known as reachable nodes.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Problem Statement🕵️‍♂️

We have given an undirected graph and a set of vertices. We have to find all reachable nodes from every node present in a given set. 

Input: An integer array ‘arr’ where arr contains the number of nodes.

Output: All the reachable nodes from a given vertex.

Example

Graph1            Graph2


Consider above an undirected graph with two disconnected components.

Input: array[ ] = { 1, 3, 5 }

Output: 

Reachable nodes from node2 are 1, 2, 3, and 4.

Reachable nodes from node3 are 1, 2, 3, and 4.

Reachable nodes from node5 are 5, 6, and 7.

Approach👩‍💻

📝 Simple Approach

  • A simple approach to solve this problem is to perform a BFS traversal for every node present in the Set and find all the reachable nodes.
     
  • But the problem with BFS traversal is that we have to call BSF separately for each node without using the visited array of the last traversal because this same vertex will be printed multiple times.
     
  • The time complexity will be O(n * (V + E)). This approach is appropriate, but when E = Θ(V2) and n = V, time complexity becomes O(V3), in which E is the no. of edges in a graph and V is the number of nodes in the graph.
     

📝Optimistic Approach

  • As the graph is undirected, all the nodes belonging to similar components will have the same reachable nodes. Therefore, we will keep track of the mapping of nodes and components.
     
  • Each component in a graph has a number, and each node in this component has this number.
     
  • For this, we use a visited array to keep note of visited nodes in BFS.
     
For node x,
If visited[x] is 0, then
x is unvisited.
else
Visited[x] represents the component number.

 

  • For any two nodes, say 'x' and 'y' if they belong to the same component, then visited[x] == visited [y]. 
     
  • For storing reachable nodes, we will use map 'm' with its key as a component number and value as a vector to keep all the reachable nodes.
     
  • For finding reachable nodes for node x return m[visited[x]].
     

    Pseudocode:

componentNumber = 0
for i=1 to n
      If visited[i] is NOT 0 the
componentNumber++


/* function BFS() returns a list 
for given node ‘i’ */
List = BFS(i, componentNumber)
m[visited[i]] = list

Solution

Let us look for the solution for finding all reachable nodes from every node present in a given set.

💥C++ 

#include <bits/stdc++.h>
using namespace std;
 
/* This class represents a directed graph using
 adjacency list representation */
class UGraph
{
public:
    int V;    // No. of vertices
 
    /* Pointer to an array containing adjacency lists */
    list<int> *adj;
 
    UGraph(int );  // Constructor
 
    void insert_edge(int, int);
 
    vector<int> BFS(int, int, int []);
};
 
UGraph::UGraph(int V)
{
    this->V = V;
    adj = new list<int>[V+1];
}
 
void UGraph::insert_edge(int x, int y)
{
    adj[x].push_back(y); // Add w to y’s list.
    adj[y].push_back(x); // Add y to w’s list.
}
 
vector<int> UGraph::BFS(int componentNumber, int src,
                                    int visited[])
{
    /* Mark all the vertices as not visited
     Create a queue for BFS */
    queue<int> queue;
 
    queue.push(src);
 
    /* Assign Component Number */
    visited[src] = componentNumber;
 
    /* Vector to keep all the reachable nodes from 'src' */
    vector<int> reachableNodes;
 
    while(!queue.empty())
    {
        /* Dequeue a vertex from queue */
        int x = queue.front();
        queue.pop();
 
        reachableNodes.push_back(x);
 
        /* Get all adjacent vertices of the dequeued
         vertex u. If an adjacent has not been visited,
         then mark it visited and enqueue it */
        for (auto itr = adj[x].begin();
                itr != adj[x].end(); itr++)
        {
            if (!visited[*itr])
            {
                /* Assign Component Number to all the
                 reachable nodes */
                visited[*itr] = componentNumber;
                queue.push(*itr);
            }
        }
    }
    return reachableNodes;
}
 
/* show all the Reachable Nodes from a node 'n' */
void showReachableNodes(int n,
            unordered_map <int, vector<int> > m)
{
    vector<int> tmpr = m[n];
/* for loop */
    for (int i=0; i<tmpr.size(); i++)
        cout << tmpr[i] << " ";
 /* printing*/
    cout << endl;
}
 
/* search all the reachable nodes for each element
 in the arr */
void findReachableNodes(UGraph ug, int arr[], int n)
{
    /* Get the no. of nodes in the graph */
    int V = ug.V;
 
    /* Take an integer visited array and initialize
     all the elements with 0 */
    int visited[V+1];
    memset(visited, 0, sizeof(visited));
 
    /* Map to store a list of reachable Nodes for a
    given node. */
    unordered_map <int, vector<int> > m;
 
    /* Initialize component Number with 0 */
    int componentNumber = 0;
 
    /* For each node in arr[] find reachable
    Nodes */
    for (int i = 0 ; i < n ; i++)
    {
        int x = arr[i];
 
        /* Visit all the nodes of the component */
        if (!visited[x])
        {
            componentNumber++;
 
            /* Store the reachable Nodes corresponding to
             the node 'i' */
            m[visited[x]] = ug.BFS(componentNumber, x, visited);
        }
 
        /* Now, we have all reachable nodes
         from x; print them by looking up in map m. */
        cout << "Reachable Nodes from " << x <<" are\n";
        showReachableNodes(visited[x], m);
    }
}
 
/* main */
int main()
{
    /* Create a graph given in the diagram above */
    int V = 7;
    UGraph ug(V);
    ug.insert_edge(1, 2);
    ug.insert_edge(2, 3);
    ug.insert_edge(3, 4);
    ug.insert_edge(3, 1);
    ug.insert_edge(5, 6);
    ug.insert_edge(5, 7);
 
    /* For every ith element in the arr
     find all reachable nodes from query[i] */
    int arr[] = {2, 3, 7};
 
    /* Find the number of elements in Set */
    int n = sizeof(arr)/sizeof(int);
 
    findReachableNodes(ug, arr, n);
 
    return 0;
}


Output:

Reachable Nodes from 2 are
2 1 3 4 
Reachable Nodes from 3 are
2 1 3 4 
Reachable Nodes from 7 are
7 5 6 


💥Python

from collections import deque
 
def insert_edge(x, y):
     
    global visited, adj
    adj[x].append(y)
    adj[y].append(x)
 
def BFS(componentNumber, src):
     
    global visited, adj
     
    # Mark all the vertices as not visited
    # Create a queue for BFS
    #a =  visited
    queue = deque()
 
    queue.append(src)
 
    # Assign Component Number
    visited[src] = 1
 
    # Vector to store all the reachable
    # nodes from 'src'
    reachableNodes = []
    #print("0:",visited)
 
    while (len(queue) > 0):
         
        # Dequeue a vertex from queue
        u = queue.popleft()
 
        reachableNodes.append(u)
 
        # Get all adjacent vertices of the dequeued
        # vertex u. If an adjacent has not been visited,
        # then mark it visited and enqueue it
        for itr in adj[u]:
            if (visited[itr] == 0):
                 
                # Assign Component numbers to all the
                # reachable nodes
                visited[itr] = 1
                queue.append(itr)
 
    return reachableNodes
 
# Display all the Reachable Nodes
# from a node 'n'
def showReachableNodes(m):
     
    for i in m:
        print(i, end = " ")
 
    print()
 # search reachable nodes
def findReachableNodes(arr, n):
     
    global V, adj, visited
     
    # Get the no. of nodes in the graph
 
    # Map to store the list of reachable Nodes for a
    # given node.
    a = []
 
    # Initialize component Number with 0
    componentNumber = 0
 
    # For each node in arr[], find reachable
    # Nodes
    for i in range(n):
        x = arr[i]
 
        # Visit all the nodes of the component
        if (visited[x] == 0):
            componentNumber += 1
 
            # Store the reachable Nodes corresponding
            # to the node'  i'
            a = BFS(componentNumber, x)
 
        # Now, we have all reachable nodes
        # from x, print them by doing a lookup in map m.
        print("Reachable Nodes from ", x, " our")
        showReachableNodes(a)
 
# main
if __name__ == '__main__':
    #declaring   
    V = 7
    adj = [[] for i in range(V + 1)]
    #visited node
    visited = [0 for i in range(V + 1)]
    insert_edge(1, 2)
    insert_edge(2, 3)
    insert_edge(3, 4)
    insert_edge(3, 1)
    insert_edge(5, 6)
    insert_edge(5, 7)
 
    # For every ith element in the arr
    # find all reachable nodes from query[i]
    arr = [ 2, 3, 7 ]
 
    # Find a number of elements in Set
    n = len(arr)
 
    findReachableNodes(arr, n)


Output:

Reachable Nodes from  2  our
2 1 3 4 
Reachable Nodes from  3  our
2 1 3 4 
Reachable Nodes from  7  our
7 5 6 

💥Complexities

✳️Time complexity: 

  • For finding all reachable nodes from every node present in a given set, the Time complexity will be O(V+E). Where V is the no. of nodes, E is the number of edges and n is the size of a given set.
     
  • In the worst case, all the V nodes are shown for each node, meaning only one component is present in the graph, so it will take O(n*V). The worst Time complexity for finding all reachable nodes from every node present in a given set is O(V+E) + O(n*V).
     

✳️Space complexity: Space complexity for finding all reachable nodes from every node present in a given set will be O(V).

Frequently Asked Questions

What is Graph?

A graph data structure is a non-linear data structure that contains two non-empty sets of vertices and edges.

Why are graphs important data structures?

Because they can easily represent the relations between real-life data.

What does a reachable node mean?

When two nodes are connected directly, they are known as reachable nodes.

What is the time complexity to find all reachable nodes from every node present in a given set?

For finding all reachable nodes from every node present in a given set, the Time complexity will be O(V+E). Where V is the no. of nodes, E is the number of edges and n is the size of a given set.

What is BFS traversal?

BFS stands for Breadth-First Search. BFS is an algorithm for searching or traversing tree or graph data structures.

Conclusion

In this article, we have discussed the solution to find all reachable nodes from every node present in a given set. We started with the problem statement, then saw examples to understand, then the approach, and finally, the solution.

Can you now solve Cycle detection in an undirected graph?

You can check out some articles related to this topic as well:


Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive ProgrammingJavaScriptSystem Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Happy learning, Ninja🥷

Previous article
Number of distinct Shortest Paths from Node 1 to N in a Weighted and Directed Graph
Next article
Calculate the number of sink nodes in a graph
Live masterclass