Parcours en profondeur et composantes connexes

L'idée principale de la recherche en profondeur d'abord est de prendre d'abord un sommet non visité comme sommet de départ, puis de suivre les arêtes du sommet courant pour se déplacer vers un sommet non visité. Lorsqu'il n'y a aucun sommet non visité, on revient au sommet précédent et on continue à essayer d'autres sommets jusqu'à ce que tous les sommets aient été visités.

Le graphe dans l'exemple ci-dessous commence le parcours à partir de 0, et l'ordre est indiqué dans la figure de droite :

Un sous-graphe connexe maximal d'un graphe non orienté G est appelé composante connexe (ou branche connexe) de G. Un graphe connexe n'a qu'une seule composante connexe, à savoir lui-même ; un graphe non orienté non connexe possède plusieurs composantes connexes. Il n'y a pas d'arêtes entre les composantes connexes. La recherche en profondeur d'abord peut être utilisée pour trouver les composantes connexes.

L'exemple suivant utilise la recherche des composantes connexes pour implémenter le parcours en profondeur d'un graphe, appelé dfs. Dans l'extrait de code ci-dessous, le tableau visited enregistre si un nœud a été visité pendant dfs, ccount enregistre le nombre de composantes connexes, le tableau id représente l'étiquette de composante connexe correspondant à chaque nœud, et deux nœuds ayant la même valeur id signifie qu'ils appartiennent à la même composante connexe.

...
// Constructeur, trouver les composantes connexes d'un graphe non pondéré
public Components(Graph graph){
    // Initialisation de l'algorithme
    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;
    }
    // Trouver les composantes connexes du graphe
    for( int i = 0 ; i < G.V() ; i ++ )
        if( !visited[i] ){
            dfs(i);
            ccount ++;
        }
}
...

Le parcours en profondeur d'un graphe est un processus récursif ; code d'implémentation :

...
// Parcours en profondeur du graphe
void dfs( int v ){

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

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

Exemple de code Java

Téléchargement du paquet de code source :Télécharger

Code du fichier src/example/graph/Components.java :

package example.graph;

import example.graph.read.Graph;

/**
* Parcours en profondeur
 */

public class Components {

    Graph G;                    // Référence au graphe
    private boolean[] visited;  // Enregistre si un nœud est visité pendant le DFS
    private int ccount;         // Enregistre le nombre de composantes connexes
    private int[] id;           // L'étiquette de composante connexe correspondant à chaque nœud

    // Parcours en profondeur du graphe
    void dfs( int v ){

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

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

    // Constructeur, trouver les composantes connexes d'un graphe non pondéré
    public Components(Graph graph){

        // Initialisation de l'algorithme
        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;
        }

        // Trouver les composantes connexes du graphe
        for( int i = 0 ; i < G.V() ; i ++ )
            if( !visited[i] ){
                dfs(i);
                ccount ++;
            }
    }

    // Renvoie le nombre de composantes connexes du graphe
    int count(){
        return ccount;
    }

    // Vérifie si le nœud v et le nœud w sont connectés
    boolean isConnected( int v , int w ){
        assert v >= 0 && v < G.V();
        assert w >= 0 && w < G.V();
        return id[v] == id[w];
    }
}
autres extensions