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 :
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];
}
}