Program to print all the non-reachable nodes | Using BFS

0 0 6 minutes read

Given an undirected graph and a set of vertices, we have to print all the non-reachable nodes from the given head node using a breadth-first search.

For example:

Consider below undirected graph with two disconnected components:

In this graph, if we consider 0 as a head node, then the node 0, 1 and 2 are reachable. We mark all the reachable nodes as visited. All those nodes which are not marked as visited i.e, node 3 and 4 are non-reachable nodes.

Examples:

Input: 5
       0 1
       0 2
       1 2
       3 4
Output: 3 4

Input: 8
       0 1
       0 2
       1 2
       3 4
       4 5
       6 7
Output: 3 4 5 6 7

Approach:

We can either use BFS or DFS for this purpose. Set 1 of this article implements the DFS approach. In this article, BFS approach is used.
We do BFS from a given source. Since the given graph is undirected, all the vertices that belong to the disconnected component are non-reachable nodes. We use the visited array for this purpose, the array which is used to keep track of non-visited vertices in BFS.
BFS is a traversing algorithm which starts traversing from a selected node (source or starting node) and traverses the graph layer-wise thus exploring the neighbour nodes (nodes which are directly connected to source node). Then, move towards the next-level neighbour nodes.

Below is the implementation of the above approach:

C++

// C++ program to count non-reachable nodes
// from a given source using BFS.
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to add an edge to graph
void add_edge(vector<int> adj[],
              int v, int w)
{
    // Add w to v’s list.
    adj[v].push_back(w);
 
    // Add v to w's list.
    adj[w].push_back(v);
}
 
// BFS traversal of the vertices
// reachable from starting node
void BFS(vector<int> adj[], int s,
         int v)
{
    // Mark all the vertices
    // as not visited
    bool visited[v] = { false };
 
    // Create a queue for BFS
    queue<int> q;
 
    // Mark the current node as
    // visited and enqueue it
    q.push(s);
    visited[s] = true;
 
    while (!q.empty()) {
        // Dequeue a vertex from
        // queue
        int p = q.front();
        q.pop();
 
        // Get all adjacent vertices
        // of the dequeued vertex p.
        // If a adjacent has not been
        // visited, then mark it
        // visited and enqueue it
        for (auto it = adj[p].begin();
             it != adj[p].end(); it++) {
            if (!visited[*it]) {
                visited[*it] = true;
                q.push(*it);
            }
        }
    }
    for (int i = 0; i < v; i++) {
        if (!visited[i]) {
            cout << i << " ";
        }
    }
    cout << "\n";
}
 
// Drivers code
int main()
{
    // Create a graph given in
    // the above diagram
    vector<int> adj[8];
    add_edge(adj, 0, 1);
    add_edge(adj, 0, 2);
    add_edge(adj, 1, 2);
    add_edge(adj, 3, 4);
    add_edge(adj, 4, 5);
    add_edge(adj, 6, 7);
 
    BFS(adj, 0, 8);
 
    return 0;
}

Java

// Java program to count non-reachable nodes
// from a given source using BFS.
import java.util.*;
 
class GFG{
  
// Function to add an edge to graph
static void add_edge(Vector<Integer> adj[],
              int v, int w)
{
    // Add w to v’s list.
    adj[v].add(w);
  
    // Add v to w's list.
    adj[w].add(v);
}
  
// BFS traversal of the vertices
// reachable from starting node
static void BFS(Vector<Integer> adj[], int s,
         int v)
{
    // Mark all the vertices
    // as not visited
    boolean []visited = new boolean[v];
  
    // Create a queue for BFS
    Queue<Integer> q = new LinkedList<>();
  
    // Mark the current node as
    // visited and enqueue it
    q.add(s);
    visited[s] = true;
  
    while (!q.isEmpty()) {
 
        // Dequeue a vertex from
        // queue
        int p = q.peek();
        q.remove();
  
        // Get all adjacent vertices
        // of the dequeued vertex p.
        // If a adjacent has not been
        // visited, then mark it
        // visited and enqueue it
        for (int it : adj[p]) {
            if (!visited[it]) {
                visited[it] = true;
                q.add(it);
            }
        }
    }
    for (int i = 0; i < v; i++) {
        if (!visited[i]) {
            System.out.print(i+ " ");
        }
    }
    System.out.print("\n");
}
  
// Drivers code
public static void main(String[] args)
{
    // Create a graph given in
    // the above diagram
    Vector<Integer> []adj = new Vector[8];
    for (int i = 0; i < 8; i++)
        adj[i] = new Vector<Integer>();
    add_edge(adj, 0, 1);
    add_edge(adj, 0, 2);
    add_edge(adj, 1, 2);
    add_edge(adj, 3, 4);
    add_edge(adj, 4, 5);
    add_edge(adj, 6, 7);
  
    BFS(adj, 0, 8);
  
}
}
 
// This code is contributed by sapnasingh4991

Python3

# Python3 program to count non-reachable 
# nodes from a given source using BFS 
 
# Function to add an edge to graph 
def add_edge(adj, v, w):
     
    # Add w to v’s list 
    adj[v].append(w)
 
    # Add v to w's list 
    adj[w].append(v)
 
# BFS traversal of the vertices 
# reachable from starting node 
def BFS(adj, s, v):
 
    # Mark all the vertices 
    # as not visited 
    visited = [False for i in range(v)]
 
    # Create a queue for BFS 
    q = []
 
    # Mark the current node as 
    # visited and enqueue it 
    q.append(s)
    visited[s] = True
 
    while (len(q) != 0):
       
        # Dequeue a vertex from 
        # queue 
        p = q[0]
        q.pop(0) 
 
        # Get all adjacent vertices 
        # of the dequeued vertex p. 
        # If a adjacent has not been 
        # visited, then mark it 
        # visited and enqueue it 
        for it in adj[p]:
            if (not visited[it]):
                visited[it] = True
                q.append(it)
             
    for i in range(v):
        if (not visited[i]):
            print(i, end = ' ')
             
    print()
     
# Driver code 
if __name__=='__main__':
 
    # Create a graph given in 
    # the above diagram 
    adj = [[] for i in range(8)]
     
    add_edge(adj, 0, 1)
    add_edge(adj, 0, 2) 
    add_edge(adj, 1, 2) 
    add_edge(adj, 3, 4) 
    add_edge(adj, 4, 5) 
    add_edge(adj, 6, 7) 
     
    BFS(adj, 0, 8) 
 
# This code is contributed by rutvik_56

C#

// C# program to count non-reachable nodes
// from a given source using BFS.
using System;
using System.Collections.Generic;
 
class GFG{
   
// Function to add an edge to graph
static void add_edge(List<int> []adj,
              int v, int w)
{
    // Add w to v’s list.
    adj[v].Add(w);
   
    // Add v to w's list.
    adj[w].Add(v);
}
   
// BFS traversal of the vertices
// reachable from starting node
static void BFS(List<int> []adj, int s,
         int v)
{
    // Mark all the vertices
    // as not visited
    bool []visited = new bool[v];
   
    // Create a queue for BFS
    List<int> q = new List<int>();
   
    // Mark the current node as
    // visited and enqueue it
    q.Add(s);
    visited[s] = true;
   
    while (q.Count != 0) {
  
        // Dequeue a vertex from
        // queue
        int p = q[0];
        q.RemoveAt(0);
   
        // Get all adjacent vertices
        // of the dequeued vertex p.
        // If a adjacent has not been
        // visited, then mark it
        // visited and enqueue it
        foreach (int it in adj[p]) {
            if (!visited[it]) {
                visited[it] = true;
                q.Add(it);
            }
        }
    }
    for (int i = 0; i < v; i++) {
        if (!visited[i]) {
            Console.Write(i + " ");
        }
    }
    Console.Write("\n");
}
   
// Driver's code
public static void Main(String[] args)
{
    // Create a graph given in
    // the above diagram
    List<int> []adj = new List<int>[8];
    for (int i = 0; i < 8; i++)
        adj[i] = new List<int>();
    add_edge(adj, 0, 1);
    add_edge(adj, 0, 2);
    add_edge(adj, 1, 2);
    add_edge(adj, 3, 4);
    add_edge(adj, 4, 5);
    add_edge(adj, 6, 7);
   
    BFS(adj, 0, 8);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program to count non-reachable
// nodes from a given source using BFS
 
// Function to add an edge to graph
function add_edge(adj, v, w){
     
    // Add w to v’s list
    adj[v].push(w)
 
    // Add v to w's list
    adj[w].push(v)
}
 
// BFS traversal of the vertices
// reachable from starting node
function BFS(adj, s, v){
 
    // Mark all the vertices
    // as not visited
    let visited = new Array(v).fill(false)
 
    // Create a queue for BFS
    let q = []
 
    // Mark the current node as
    // visited and enqueue it
    q.push(s)
    visited[s] = true
 
    while (q.length != 0){
     
        // Dequeue a vertex from
        // queue
        let p = q.shift()
 
        // Get all adjacent vertices
        // of the dequeued vertex p.
        // If a adjacent has not been
        // visited, then mark it
        // visited and enqueue it
        for(let it of adj[p]){
            if (!visited[it]){
                visited[it] = true
                q.push(it)
            }
        }
    }
             
    for(let i=0;i<v;i++){
        if (!visited[i]){
            document.write(i,' ')
        }
    }
             
    document.write("</br>")
}
     
// Driver code
 
// Create a graph given in
// the above diagram
let adj = new Array(8)
for(let i=0;i<8;i++){
    adj[i] = new Array()
}
 
add_edge(adj, 0, 1)
add_edge(adj, 0, 2)
add_edge(adj, 1, 2)
add_edge(adj, 3, 4)
add_edge(adj, 4, 5)
add_edge(adj, 6, 7)
 
BFS(adj, 0, 8)
 
// This code is contributed by Shinjanpatra
 
</script>

Output:

3 4 5 6 7

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!