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 graphvoid 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 nodevoid 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 codeint 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 graphstatic 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 nodestatic 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 codepublic 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 graphstatic 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 nodestatic 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 codepublic 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 graphfunction 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 nodefunction 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 diagramlet 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
