Algorithme de recherche de chemin

L'algorithme de recherche de chemin dans un graphe peut également être implémenté à l'aide d'une recherche en profondeur d'abord (DFS), en trouvant les chemins d'un point de départ s vers d'autres points du graphe. Dans la classe d'implémentation de la sous-section précédente, ajoutez un tableau global `from` pour enregistrer les chemins ; `from[i]` représente le nœud précédent de `i` sur le chemin trouvé.

Tout d'abord, le constructeur initialise les conditions initiales de l'algorithme de recherche de chemin,from = new int[G.V()]etfrom = new int[G.V()]et définit les valeurs par défaut dans une boucle : toutes les valeurs du tableau `visited` sont `false`, et toutes les valeurs du tableau `from` sont `-1`. Ensuite, un traitement DFS récursif est effectué sur le nœud de départ.

...
// Constructeur, algorithme de recherche de chemin, trouve les chemins du point s vers d'autres points du graphe
public Path(Graph graph, int s){
    // Initialisation de l'algorithme
    G = graph;
    assert s >= 0 && s < G.V();
    visited = new boolean[G.V()];
    from = new int[G.V()];
    for( int i = 0 ; i < G.V() ; i ++ ){
        visited[i] = false;
        from[i] = -1;
    }
    this.s = s;
    // Algorithme de recherche de chemin
    dfs(s);
}
...

Pour déterminer s'il existe un chemin du point s au point w, il suffit de vérifier la valeur correspondante dans le tableau `visited`.

...
boolean hasPath(int w){
    assert w >= 0 && w < G.V();
    return visited[w];
}
...

Pour obtenir le chemin spécifique de s à w, nous l'implémentons à l'aide de la méthode `path`. Tout d'abord, déterminez s'ils sont connectés en appelant la méthode `hasPath`. Comme on peut le voir d'après le constructeur, tous les chemins peuvent être trouvés simplement en remontant à travers le tableau `from`.

...
Vector<Integer> path(int w){
    assert hasPath(w) ;
    Stack<Integer> s = new Stack<Integer>();
    // En parcourant le tableau from, remonter le chemin de s à w et le stocker dans la pile
    int p = w;
    while( p != -1 ){
        s.push(p);
        p = from[p];
    }
    // Retirer les éléments de la pile un par un pour obtenir le chemin ordonné de s à w
    Vector<Integer> res = new Vector<Integer>();
    while( !s.empty() )
        res.add( s.pop() );
    return res;
}
...

Exemple de code Java

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

Code dans src/example/graph/Path.java :

package example.graph;

import example.graph.read.Graph;

import java.util.Stack;
import java.util.Vector;

/**
* Recherche de chemin
 */

public class Path {
    // Référence au graphe
    private Graph G;
    // Point de départ
    private int s;
    // Enregistrer si un nœud est visité pendant le DFS
    private boolean[] visited;
    // Enregistrer le chemin ; from[i] représente le nœud précédent de i sur le chemin de recherche
    private int[] from;

    // Parcours en profondeur du graphe
    private void dfs( int v ){
        visited[v] = true;
        for( int i : G.adj(v) )
            if( !visited[i] ){
                from[i] = v;
                dfs(i);
            }
    }

    // Constructeur, algorithme de recherche de chemin, trouve les chemins du point s vers d'autres points du graphe
    public Path(Graph graph, int s){
        // Initialisation de l'algorithme
        G = graph;
        assert s >= 0 && s < G.V();
        visited = new boolean[G.V()];
        from = new int[G.V()];
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            from[i] = -1;
        }
        this.s = s;
        // Algorithme de recherche de chemin
        dfs(s);
    }

    // Vérifier s'il existe un chemin du nœud s au nœud w
    boolean hasPath(int w){
        assert w >= 0 && w < G.V();
        return visited[w];
    }

    // Rechercher le chemin du nœud s au nœud w et le stocker dans vec
    Vector<Integer> path(int w){

        assert hasPath(w) ;

        Stack<Integer> s = new Stack<Integer>();
        // En parcourant le tableau from, remonter le chemin de s à w et le stocker dans la pile
        int p = w;
        while( p != -1 ){
            s.push(p);
            p = from[p];
        }

        // Retirer les éléments de la pile un par un pour obtenir le chemin ordonné de s à w
        Vector<Integer> res = new Vector<Integer>();
        while( !s.empty() )
            res.add( s.pop() );

        return res;
    }

    // Afficher le chemin du nœud s au nœud w
    void showPath(int w){

        assert hasPath(w) ;

        Vector<Integer> vec = path(w);
        for( int i = 0 ; i < vec.size() ; i ++ ){
            System.out.print(vec.elementAt(i));
            if( i == vec.size() - 1 )
                System.out.println();
            else
                System.out.print(" -> ");
        }
    }
}
autres extensions