data-structures
Recorridos de grafos
Buscar..
Introducción
Todos los algoritmos relacionados con los recorridos gráficos. Sus complejidades, tanto en tiempo de ejecución como en espacio.
Primera búsqueda de profundidad
La profundidad del primer recorrido (o búsqueda) para un gráfico es similar a la profundidad del primer recorrido de un árbol. La única captura aquí es que, a diferencia de los árboles, los gráficos pueden contener ciclos, por lo que podemos llegar al mismo nodo nuevamente. Para evitar procesar un nodo más de una vez, usamos una matriz visitada booleana.
El siguiente algoritmo presenta los pasos para el recorrido del gráfico utilizando DFS:
Algoritmo DFS (v);
Entrada : un vértice v en una gráfica
Salida : Un etiquetado de los bordes como bordes de "descubrimiento" y "aristas".
for each edge e incident on v do
if edge e is unexplored then
let w be the other endpoint of e
if vertex w is unexplored then
label e as a discovery edge
recursively call DFS(w)
else
label e as a backedge
Amplia primera búsqueda
Algoritmo BFS (G)
Gráfico de entrada G
Etiquetado de salida de los bordes y partición de los vértices de G.
for all u ∈ G.vertices()
setLabel(u, UNEXPLORED)
for all e ∈ G.edges()
setLabel
(e, UNEXPLORED)
for all v ∈ G.vertices()
if getLabel(v) = UNEXPLORED
BFS(G, v)
