Please enable JavaScript.
Coggle requires JavaScript to display documents.
Atravesando un gráfico: BFS y DFS, image, image, image, image, image,…
Atravesando un gráfico: BFS y DFS
Búsqueda en amplitud (BFS)
• Usamos una cola Q para contener todos los vértices grises: vértices que hemos visto pero con los que aún no hemos terminado.
• Recordamos desde qué vértice un vértice dado v está coloreado en gris – es decir, el nodo que descubrió v primero; esto se llama
padre [v]
• También mantenemos d[v], la longitud del camino de s a v. Inicialmente d[s] = 0
Propiedades
• Durante BFS(v) cada borde en G se clasifica como:
borde de árbol: un borde que conduce a un vértice no marcado
borde que no es de árbol: un borde que conduce a un vértice marcado
• Cada vértice, excepto los vértices de origen, tiene un padre; estos bordes (v, padre [v]) definen un árbol, llamado árbol BFS.
• Lema: En un gráfico dirigido, BFS(s) alcanza todos los vértices alcanzables desde s. En un gráfico no dirigido:
BFS(s)visita todos los vértices en el componente conectado (CC) de s, y el árbol BFS obtenido es un árbol de expansión de
CC(s).
• Lema: BFS(s) se ejecuta en O(|Vc| + |Ec|), donde Vc, Ec son el número de vértices y aristas en CC(s). Cuando se ejecuta en todo el gráfico, BFS(G) se ejecuta en tiempo O(|V | + |E|). Dicho de otra manera, BFS se ejecuta en tiempo lineal en
el tamaño del gráfico
• Lema: Sea x un vértice alcanzado en BFS(s). Su distancia d[x] representa el camino más corto de s a x en G.
Idea de prueba: todos los vértices v que están a una arista de distancia de s se descubren al explorar s y se establecen
con d[v] = 1.
Búsqueda en profundidad (DFS)
• Utilice pila en lugar de cola para contener los vértices descubiertos
– Vamos “lo más profundo posible”, retrocedemos hasta encontrar el primer vértice adyacente inexplorad
• Útil para calcular la “hora de inicio” y la “hora de finalización” del vértice u
Hora de inicio d[u]: hora en la que se visita un vértice por primera vez
– Hora de finalización f[u]: hora en la que se han visitado todos los vértices adyacentes de u.
• Podemos escribir DFS iterativamente usando el mismo algoritmo que para BFS pero con un STACK
de una COLA, o podemos escribir un procedimiento DFS recursivo
PROPIEDADES
• DFS(u) alcanza todos los vértices alcanzables desde u. En gráficos no dirigidos, DFS(u) visita todos los vértices en CC(u), y
el árbol DFS obtenido es un árbol de expansión de G.
• Análisis: DFS(s) se ejecuta en O(|Vc| + |Ec|), donde Vc, Ec son el número de vértices y aristas en CC(s) (accesibles desde s,
para gráficos dirigidos)
• Al igual que BFS (v, parent[v]) forma un árbol, el árbol DF
• Anidamiento de descendientes: si u es descendiente de v en el árbol DFS, entonces d[v] < d[u] < f[u] < f[v
Kelvin Ronny Quispe Bravo
