Programa para contar Número de componentes conectados en un gráfico no dirigido

Dado un gráfico g no dirigido , la tarea es imprimir el número de componentes conectados en el gráfico.

Ejemplos:  

Aporte: 
 

Salida: 3 
Hay tres componentes conectados: 
1 – 5, 0 – 2 – 4 y 3 

Acercarse: 

DFS visita todos los vértices conectados del vértice dado.

Al iterar sobre todos los vértices, cada vez que vemos un Node no visitado, es porque DFS no lo visitó en los vértices hasta el momento.

Eso significa que no está conectado a ningún Node anterior visitado hasta el momento, es decir, no formaba parte de componentes anteriores.

Por lo tanto, este Node pertenece al nuevo componente.

Esto significa que, antes de visitar este Node, terminamos de visitar el componente anterior de todos los Nodes y ese componente ahora está completo.

Entonces, necesitamos incrementar el contador de componentes a medida que completamos un componente.

La idea es usar una cuenta variable para almacenar la cantidad de componentes conectados y realizar los siguientes pasos:

Inicialice todos los vértices como no visitados.
Para todos los vértices, verifique si un vértice no ha sido visitado , luego realice DFS en ese vértice e incremente la cuenta variable en 1 .

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Graph class represents a undirected graph
// using adjacency list representation
class Graph {
    // No. of vertices
    int V;
 
    // Pointer to an array containing adjacency lists
    list<int>* adj;
 
    // A function used by DFS
    void DFSUtil(int v, bool visited[]);
 
public:
    // Constructor
    Graph(int V);
 
    void addEdge(int v, int w);
    int NumberOfconnectedComponents();
};
 
// Function to return the number of
// connected components in an undirected graph
int Graph::NumberOfconnectedComponents()
{
 
    // Mark all the vertices as not visited
    bool* visited = new bool[V];
 
    // To store the number of connected components
    int count = 0;
    for (int v = 0; v < V; v++)
        visited[v] = false;
 
    for (int v = 0; v < V; v++) {
        if (visited[v] == false) {
            DFSUtil(v, visited);
            count += 1;
        }
    }
 
    return count;
}
 
void Graph::DFSUtil(int v, bool visited[])
{
 
    // Mark the current node as visited
    visited[v] = true;
 
    // Recur for all the vertices
    // adjacent to this vertex
    list<int>::iterator i;
 
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
 
// Add an undirected edge
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
    adj[w].push_back(v);
}
 
// Driver code
int main()
{
    Graph g(5);
    g.addEdge(1, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 4);
 
    cout << g.NumberOfconnectedComponents();
 
    return 0;
}

import java.util.*;
class Graph {
    private int V; // No. of vertices in graph.
 
    private LinkedList<Integer>[] adj; // Adjacency List
                                       // representation
 
    ArrayList<ArrayList<Integer> > components
        = new ArrayList<>();
 
    @SuppressWarnings("unchecked") Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
 
        for (int i = 0; i < v; i++)
            adj[i] = new LinkedList();
    }
 
    void addEdge(int u, int w)
    {
        adj[u].add(w);
        adj[w].add(u); // Undirected Graph.
    }
 
    void DFSUtil(int v, boolean[] visited,
                 ArrayList<Integer> al)
    {
        visited[v] = true;
        al.add(v);
        System.out.print(v + " ");
        Iterator<Integer> it = adj[v].iterator();
 
        while (it.hasNext()) {
            int n = it.next();
            if (!visited[n])
                DFSUtil(n, visited, al);
        }
    }
 
    void DFS()
    {
        boolean[] visited = new boolean[V];
 
        for (int i = 0; i < V; i++) {
            ArrayList<Integer> al = new ArrayList<>();
            if (!visited[i]) {
                DFSUtil(i, visited, al);
                components.add(al);
            }
        }
    }
 
    int ConnecetedComponents() { return components.size(); }
}
public class Main {
    public static void main(String[] args)
    {
        Graph g = new Graph(6);
 
        g.addEdge(1, 5);
        g.addEdge(0, 2);
        g.addEdge(2, 4);
        System.out.println("Graph DFS:");
        g.DFS();
        System.out.println(
            "\nNumber of Conneceted Components: "
            + g.ConnecetedComponents());
    }
}
// Code contributed by Madhav Chittlangia.

# Python3 program for above approach
 
# Graph class represents a undirected graph
# using adjacency list representation
class Graph:
     
    def __init__(self, V):
 
        # No. of vertices
        self.V = V
 
        # Pointer to an array containing
        # adjacency lists
        self.adj = [[] for i in range(self.V)]
 
    # Function to return the number of
    # connected components in an undirected graph
    def NumberOfconnectedComponents(self):
         
        # Mark all the vertices as not visited
        visited = [False for i in range(self.V)]
         
        # To store the number of connected
        # components
        count = 0
         
        for v in range(self.V):
            if (visited[v] == False):
                self.DFSUtil(v, visited)
                count += 1
                 
        return count
         
    def DFSUtil(self, v, visited):
 
        # Mark the current node as visited
        visited[v] = True
 
        # Recur for all the vertices
        # adjacent to this vertex
        for i in self.adj[v]:
            if (not visited[i]):
                self.DFSUtil(i, visited)
                 
    # Add an undirected edge
    def addEdge(self, v, w):
         
        self.adj[v].append(w)
        self.adj[w].append(v)
         
# Driver code       
if __name__=='__main__':
     
    g = Graph(5)
    g.addEdge(1, 0)
    g.addEdge(2, 3)
    g.addEdge(3, 4)
     
    print(g.NumberOfconnectedComponents())
 
# This code is contributed by rutvik_56

<script>
 
// JavaScript program for above approach
 
// Graph class represents a undirected graph
// using adjacency list representation
class Graph{
     
    constructor(V){
 
        // No. of vertices
        this.V = V
 
        // Pointer to an array containing
        // adjacency lists
        this.adj = new Array(this.V);
        for(let i=0;i<V;i++){
            this.adj[i] = new Array()
        }
    }
 
    // Function to return the number of
    // connected components in an undirected graph
    NumberOfconnectedComponents(){
         
        // Mark all the vertices as not visited
        let visited = new Array(this.V).fill(false);
         
        // To store the number of connected
        // components
        let count = 0
         
        for(let v=0;v<this.V;v++){
            if (visited[v] == false){
                this.DFSUtil(v, visited)
                count += 1
            }
        }
                 
        return count
    }
 
    DFSUtil(v, visited){
 
        // Mark the current node as visited
        visited[v] = true;
 
        // Recur for all the vertices
        // adjacent to this vertex
        for(let i of this.adj[v]){
            if (visited[i] == false){
                this.DFSUtil(i, visited)
            }
        }  
     
    }
                 
    // Add an undirected edge
    addEdge(v, w){
        this.adj[v].push(w)
        this.adj[w].push(v)
    }
     
}
         
// Driver code   
let g = new Graph(5)
g.addEdge(1, 0)
g.addEdge(2, 3)
g.addEdge(3, 4)
 
document.write(g.NumberOfconnectedComponents(),"</br>")
 
// This code is contributed by shinjanpatra
</script>

2

Análisis de Complejidad:

Complejidad temporal: O(V + E), donde V es el número de vértices y E es el número de aristas del grafo.
Complejidad espacial: O(V), ya que se requiereuna array extra visitada de tamaño V.