Recorrer un
grafo significa tratar de alcanzar todos los nodos que estén relacionados.
1. El Camino Más Corto:
El algoritmo
de Dijkstra resuelve el problema de encontrar los caminos más cortos a partir
de un origen, en grafos pesados que no tengan pesos negativos. El algoritmo
de Dijkstra es un algoritmo voraz que
opera a partir de un conjunto S de nodos cuya distancia más corta desde el
origen ya es conocida. En principio, S contiene solo el nodo origen. En cada
paso, se agrega algún nodo v a S, cuya distancia desde el origen es la más
corta posible. Bajo la hipótesis de que los pesos son no negativos, siempre es
posible encontrar un camino más corto entre el origen y v que pasas sólo a
través de los nodos de S, al que llamaremos “especial” más corto a cada nodo.
Una vez que S incluye todos los nodos, todos los caminos son “especiales”, así
que D contendrá la distancia más corta del origen a cada vértice. Se puede
utilizar un arreglo P, para ir almacenamiento los caminos más cortos.
2. A Lo Ancho:
En este
algoritmo también se utiliza la estrategia de marcas los nodos como “visitados”
para detectar la culminación del recorrido, pero los nodos se recorren de una
manera ligeramente distinta. Este algoritmo puede crear menos ambientes
recursivos que le anterior porque visita más nodos en un mismo ambiente, pero
esto depende de cómo este construido el grafo. El algoritmo se conoce como el
algoritmo de BFS (Breadth-First Search).
3. En Profundidad:
Para
efectuar un recorrido en profundidad de un grafo, se selecciona cualquier nodo
como punto de partida (por lo general el primer nodo del grafo) y se marcan
todos los nodos del grafo como “no visitados”. El nodo inicial se marca como
“visitado” y si hay un nodo adyacente a este que no haya sido “visitado”, se
toma este nodo como nuevo punto de partida del recorrido. El recorrido culmina
cuando todos los nodos hayan sido visitados.
REFERENCIA:
Toledo, I. (11 de Octubre de 2012). Teoria de Grafos.
Obtenido de SlideShare.net: http://es.slideshare.net/isaiastoledo7/teora-de-grafos-14694334
No hay comentarios:
Publicar un comentario