Algoritmo de búsqueda de rutas

El algoritmo de búsqueda de rutas de un grafo también se puede implementar mediante el recorrido en profundidad dfs, encontrando la ruta desde el punto inicial s hasta otros puntos en el grafo graph. En la clase de implementación de la sección anterior, añade la variable global from (array) para registrar la ruta; from[i] representa el nodo anterior de i en la ruta buscada.

Primero, el constructor inicializa las condiciones iniciales del algoritmo de búsqueda de rutas,from = new int[G.V()]yfrom = new int[G.V()]y en el bucle establece los valores predeterminados: el array visited está todo en false, el array from está todo en -1, y luego se realiza el procesamiento recursivo de dfs sobre el nodo inicial.

...
// Constructor, algoritmo de búsqueda de rutas, encuentra la ruta desde el punto s hasta otros puntos en el grafo graph
public Path(Graph graph, int s){
    // Inicialización del algoritmo
    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;
    // Algoritmo de búsqueda de rutas
    dfs(s);
}
...

Entonces, para determinar si hay una ruta desde el punto s hasta el punto w, basta con consultar el valor correspondiente del array visited.

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

Para obtener la ruta específica desde el punto s hasta el punto w, la implementamos con el método path. Primero se determina si están conectados; se puede llamar al método hasPath. Según el constructor, solo hay que rastrear hacia atrás a través del array from para encontrar todas las rutas.

...
Vector<Integer> path(int w){
    assert hasPath(w) ;
    Stack<Integer> s = new Stack<Integer>();
    // A través del array from, encuentra inversamente la ruta desde s hasta w y guárdala en la pila
    int p = w;
    while( p != -1 ){
        s.push(p);
        p = from[p];
    }
    // Extrae los elementos de la pila uno a uno para obtener la ruta ordenada de s a w
    Vector<Integer> res = new Vector<Integer>();
    while( !s.empty() )
        res.add( s.pop() );
    return res;
}
...

Código de ejemplo en Java

Descargar paquete de código fuente:Download

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

package ejemplo.graph;

import ejemplo.graph.read.Graph;

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

/**
* Búsqueda de rutas
 */
public class Path {
    // Referencia al grafo
    private Graph G;
    // Punto inicial
    private int s;
    // Registra si el nodo ha sido visitado durante el proceso de dfs
    private boolean[] visited;
    // Registra la ruta; from[i] representa el nodo anterior de i en la ruta buscada
    private int[] from;

    // Recorrido en profundidad del grafo
    private void dfs( int v ){
        visited[v] = true;
        for( int i : G.adj(v) )
            if( !visited[i] ){
                from[i] = v;
                dfs(i);
            }
    }

    // Constructor, algoritmo de búsqueda de rutas, encuentra la ruta desde el punto s hasta otros puntos en el grafo graph
    public Path(Graph graph, int s){
        // Inicialización del algoritmo
        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;
        // Algoritmo de búsqueda de rutas
        dfs(s);
    }

    // Consulta si hay una ruta desde el punto s hasta el punto w
    boolean hasPath(int w){
        assert w >= 0 && w < G.V();
        return visited[w];
    }

    // Consulta la ruta desde el punto s hasta el punto w y la almacena en vec
    Vector<Integer> path(int w){

        assert hasPath(w) ;

        Stack<Integer> s = new Stack<Integer>();
        // A través del array from, encuentra inversamente la ruta de s a w y la guarda en la pila
        int p = w;
        while( p != -1 ){
            s.push(p);
            p = from[p];
        }

        // Extrae los elementos de la pila uno a uno para obtener la ruta ordenada de s a w
        Vector<Integer> res = new Vector<Integer>();
        while( !s.empty() )
            res.add( s.pop() );

        return res;
    }

    // Imprime la ruta desde el punto s hasta el punto 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(" -> ");
        }
    }
}
Otras extensiones