Programa para imprimir todos los Nodes no accesibles | Usando BFS

Dado un gráfico no dirigido y un conjunto de vértices , tenemos que imprimir todos los Nodes no accesibles del Node principal dado mediante una búsqueda en anchura .

Por ejemplo:  

Considere el siguiente gráfico no dirigido con dos componentes desconectados: 
 

En este gráfico, si consideramos el 0 como un Node principal, entonces los Nodes 0, 1 y 2 son alcanzables. Marcamos todos los Nodes accesibles como visitados. Todos aquellos Nodes que no están marcados como visitados, es decir, los Nodes 3 y 4 son Nodes no accesibles. 
 

Ejemplos: 

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

Acercarse: 

• Podemos usar BFS o DFS para este propósito. El conjunto 1 de este artículo implementa el enfoque DFS. En este artículo, se utiliza el enfoque BFS.
• Hacemos BFS de una fuente determinada. Dado que el gráfico dado no está dirigido, todos los vértices que pertenecen al componente desconectado son Nodes no accesibles. Usamos la array visitada para este propósito, la array que se usa para realizar un seguimiento de los vértices no visitados en BFS. 
• BFS es un algoritmo de recorrido que comienza a recorrer desde un Node seleccionado (Node de origen o inicial) y atraviesa el gráfico por capas, explorando así los Nodes vecinos (Nodes que están directamente conectados al Node de origen). Luego, muévase hacia los Nodes vecinos del siguiente nivel. 
   

A continuación se muestra la implementación del enfoque anterior:  

// 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 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 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# 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

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

3 4 5 6 7