Publicado · en mejora
Algorithm
El recorrido de grafos visita todos los vértices alcanzables con BFS o DFS y es la base de caminos mínimos sin pesos, componentes, ciclos y orden topológico.
El recorrido de grafos consiste en visitar, exactamente una vez, todos los vértices alcanzables desde un vértice inicial siguiendo sus aristas. Las dos estrategias fundamentales son la búsqueda en anchura (BFS), que usa una cola para avanzar capa por capa, y la búsqueda en profundidad (DFS), que usa una pila o recursión para seguir un camino hasta el final antes de retroceder. Los grafos se suelen almacenar como listas de adyacencia o matrices de adyacencia, y las cuadrículas 2D, como los laberintos, también son grafos si cada celda se considera un vértice.
Las redes de carreteras, las redes sociales, las dependencias entre tareas y los enlaces web son grafos. BFS encuentra caminos mínimos cuando todas las aristas cuestan lo mismo, mientras que DFS es la base de las componentes conexas, la detección de ciclos y el orden topológico. Las herramientas de compilación que ordenan tareas, los recolectores de basura que deciden qué sigue siendo alcanzable y el bote de pintura de un editor de imágenes dependen del recorrido, y es uno de los temas más frecuentes en entrevistas técnicas.
Conviene empezar dibujando un grafo pequeño y siguiendo a mano cómo cambian la cola de BFS y la pila de llamadas de DFS. Después, implementa ambos tú mismo, prestando atención a cuándo se marcan los vértices como visitados y cómo se registran las distancias y los padres. A partir de ahí, pasa a caminos mínimos en cuadrículas, conteo de componentes conexas y orden topológico con el algoritmo de Kahn.
Las listas de adyacencia usan memoria O(V + E) y encajan con grafos dispersos; las matrices comprueban aristas en O(1) pero ocupan O(V^2).
Una cola visita primero los vértices más cercanos, así que en un grafo sin pesos la primera distancia asignada es la mínima.
La recursión o una pila avanzan en profundidad y retroceden; es la base de componentes, detección de ciclos y backtracking.
En un grafo dirigido acíclico, el algoritmo de Kahn o el orden de finalización inverso de DFS dan un orden que respeta las dependencias.
El programa construye un grafo no dirigido de seis vértices como lista de adyacencia en un diccionario y muestra, con un BFS basado en deque, el menor número de aristas desde A hasta cada vértice, y con un DFS recursivo, el orden de visita. Ambas funciones registran los vértices visitados para no procesar ninguno dos veces.
graph_traversal.py
from collections import deque
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D", "E"],
"D": ["B", "C", "F"],
"E": ["C", "F"],
"F": ["D", "E"],
}
def bfs(start):
"""Shortest number of edges from start to every reachable vertex."""
dist = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in dist:
dist[nxt] = dist[node] + 1
queue.append(nxt)
return dist
def dfs(start):
"""Vertices in depth-first visiting order."""
order, seen = [], set()
def visit(node):
seen.add(node)
order.append(node)
for nxt in graph[node]:
if nxt not in seen:
visit(nxt)
visit(start)
return order
print(bfs("A")) # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}
print(dfs("A")) # ['A', 'B', 'D', 'C', 'E', 'F']
python graph_traversal.pySeis capítulos que te llevan desde la instalación hasta las ideas clave de Recorrido de grafos.
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Recorrido de grafos.
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.