Recorrido en profundidad y componentes conexas

La idea principal del recorrido en profundidad (Depth First Search) es primero tomar un vértice no visitado como vértice inicial, y a lo largo de las aristas del vértice actual llegar a vértices no visitados. Cuando no hay vértices no visitados, se regresa al vértice anterior, y se continúa probando otros vértices, hasta que todos los vértices hayan sido visitados.

En el gráfico de ejemplo siguiente, el orden de recorrido comenzando desde 0 se muestra en la figura de la derecha:

Un subgrafo conexo maximal de un grafo no dirigido G se denomina componente conexa (o componente conexa) de G. Un grafo conexo tiene una sola componente conexa, es decir, él mismo; un grafo no dirigido no conexo tiene múltiples componentes conexas. No hay ninguna arista entre las componentes conexas. El recorrido en profundidad se puede utilizar para encontrar las componentes conexas.

A continuación, tomando como ejemplo el cálculo de componentes conexas, se implementa el recorrido en profundidad del grafo, llamado dfs. En el siguiente fragmento de código, la matriz visited registra si los nodos han sido visitados durante el proceso de dfs, ccount registra el número de componentes conexas, la matriz id representa la marca de componente conexa correspondiente a cada nodo; dos nodos con el mismo valor de id significan que pertenecen a la misma componente conexa.

...
// Constructor, calcula las componentes conexas de un grafo no ponderado
public Components(Graph graph){
    // Inicialización del algoritmo
    G = graph;
    visited = new boolean[G.V()];
    id = new int[G.V()];
    ccount = 0;
    for( int i = 0 ; i < G.V() ; i ++ ){
        visited[i] = false;
        id[i] = -1;
    }
    // Encontrar las componentes conexas del grafo
    for( int i = 0 ; i < G.V() ; i ++ )
        if( !visited[i] ){
            dfs(i);
            ccount ++;
        }
}
...

El recorrido en profundidad del grafo es un proceso recursivo, el código de implementación:

...
// Recorrido en profundidad del grafo
void dfs( int v ){

    visited[v] = true;
    id[v] = ccount;

    for( int i: G.adj(v) ){
        if( !visited[i] )
            dfs(i);
    }
}
...

Código de ejemplo en Java

Descargar paquete de código fuente:Download

Código del archivo src/ejemplo/graph/Components.java:

package ejemplo.graph;

import ejemplo.graph.read.Graph;

/**
* Recorrido en profundidad
 */

public class Components {

    Graph G;                    // Referencia del grafo
    private boolean[] visited;  // Registra si los nodos han sido visitados durante el proceso de dfs
    private int ccount;         // Registra el número de componentes conexas
    private int[] id;           // La marca de componente conexa correspondiente a cada nodo

    // Recorrido en profundidad del grafo
    void dfs( int v ){

        visited[v] = true;
        id[v] = ccount;

        for( int i: G.adj(v) ){
            if( !visited[i] )
                dfs(i);
        }
    }

    // Constructor, calcula las componentes conexas de un grafo no ponderado
    public Components(Graph graph){

        // Inicialización del algoritmo
        G = graph;
        visited = new boolean[G.V()];
        id = new int[G.V()];
        ccount = 0;
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            id[i] = -1;
        }

        // Encontrar las componentes conexas del grafo
        for( int i = 0 ; i < G.V() ; i ++ )
            if( !visited[i] ){
                dfs(i);
                ccount ++;
            }
    }

    // Devuelve el número de componentes conexas del grafo
    int count(){
        return ccount;
    }

    // Consulta si el punto v y el punto w están conectados
    boolean isConnected( int v , int w ){
        assert v >= 0 && v < G.V();
        assert w >= 0 && w < G.V();
        return id[v] == id[w];
    }
}
Otras extensiones