Recorrido en amplitud y camino más corto
El recorrido en amplitud comienza desde un vértice v; primero visita este nodo y lo marca como visitado, luego visita secuencialmente todos los nodos adyacentes no visitados de v {vi,..,vj}, los marca como visitados, y después repite el método de visita del nodo v para cada nodo en {vi,...,vj}, hasta que todos los nodos hayan sido visitados.
Podemos dividirlo en tres pasos:
- (1) Utilice una cola auxiliar q; primero ponga el vértice v en la cola, márquelo como visitado y luego verifique en un bucle si la cola está vacía.
- (2) Si la cola no está vacía, extraiga el primer elemento de la cola, ponga en la cola todos los nodos no visitados asociados con ese elemento y márquelos como visitados.
- (3) Si la cola está vacía, significa que todos los nodos ya han sido recorridos en amplitud.
Como se muestra en la siguiente figura, el azul de la derecha indica el orden de recorrido de los nodos desde 0, y abajo se registra la distancia al nodo 0. Se puede ver que el recorrido en amplitud puede encontrar el camino más corto en un grafo no ponderado.
A continuación se muestra mediante código cómo completar el recorrido usando el recorrido en amplitud y encontrar el camino más corto. Sobre la base del código de la sección anterior, añadimos una variable global, el array ord, que registra el orden de los nodos en el camino. ord[i] representa el orden del nodo i en el camino. Al mismo tiempo, el constructor se ajusta en consecuencia: al recorrer los nodos adyacentes, cada vez que se visita un nodo no visitado, se registra la distancia con ord[i] = ord[v] + 1. La complejidad temporal del recorrido en amplitud para una lista de adyacencia es O(V+E), y para una matriz de adyacencia es O(V^2).
// Constructor, algoritmo de búsqueda de caminos, encuentra el camino desde el punto s hasta otros puntos en el grafo graph
public ShortestPath(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()];
ord = new int[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
from[i] = -1;
ord[i] = -1;
}
this.s = s;
// Algoritmo de camino más corto para grafo no dirigido, recorre todo el grafo en amplitud desde s
LinkedList<Integer> q = new LinkedList<Integer>();
q.push( s );
visited[s] = true;
ord[s] = 0;
while( !q.isEmpty() ){
int v = q.pop();
for( int i : G.adj(v) )
if( !visited[i] ){
q.push(i);
visited[i] = true;
from[i] = v;
ord[i] = ord[v] + 1;
}
}
}
...
Ver la longitud del camino más corto desde el punto s hasta el punto w. Si w no es alcanzable desde s, devuelve -1.
public int length(int w){
assert w >= 0 && w < G.V();
return ord[w];
}
...
Código de ejemplo en Java
Descarga del paquete de código fuente:Download
Código del archivo src/ejemplo/graph/ShortestPath.java:
import ejemplo.graph.read.Graph;
import java.util.LinkedList;
import java.util.Stack;
import java.util.Vector;
/**
* Recorrido en amplitud y camino más corto
*/
public class ShortestPath {
// Referencia del grafo
private Graph G;
// Punto de inicio
private int s;
// Registra si el nodo ha sido visitado durante el proceso de dfs
private boolean[] visited;
// Registra el camino; from[i] indica el nodo anterior de i en el camino encontrado
private int[] from;
// Registra el orden de los nodos en el camino. ord[i] indica el orden del nodo i en el camino.
private int[] ord;
// Constructor, algoritmo de búsqueda de caminos, encuentra el camino desde el punto s hasta otros puntos en el grafo graph
public ShortestPath(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()];
ord = new int[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
from[i] = -1;
ord[i] = -1;
}
this.s = s;
// Algoritmo de camino más corto para grafo no dirigido, recorre todo el grafo en amplitud desde s
LinkedList<Integer> q = new LinkedList<Integer>();
q.push( s );
visited[s] = true;
ord[s] = 0;
while( !q.isEmpty() ){
int v = q.pop();
for( int i : G.adj(v) )
if( !visited[i] ){
q.push(i);
visited[i] = true;
from[i] = v;
ord[i] = ord[v] + 1;
}
}
}
// Consulta si hay un camino desde el punto s hasta el punto w
public boolean hasPath(int w){
assert w >= 0 && w < G.V();
return visited[w];
}
// Consulta el camino desde el punto s hasta el punto w y lo almacena en vec
public Vector<Integer> path(int w){
assert hasPath(w) ;
Stack<Integer> s = new Stack<Integer>();
// Utiliza el array from para buscar el camino de s a w en orden inverso y lo almacena en una pila
int p = w;
while( p != -1 ){
s.push(p);
p = from[p];
}
// Extrae los elementos de la pila uno por uno para obtener el camino ordenado de s a w
Vector<Integer> res = new Vector<Integer>();
while( !s.empty() )
res.add( s.pop() );
return res;
}
// Imprime el camino desde el punto s hasta el punto w
public 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(" -> ");
}
}
// Ver la longitud del camino más corto desde el punto s hasta el punto w
// Si w no es alcanzable desde s, devuelve -1
public int length(int w){
assert w >= 0 && w < G.V();
return ord[w];
}
}