9 - Recorridos en grafos

Un recorrido sirve para visitar todos los vértices que se pueden alcanzar desde un punto. Aquí se explica qué son, cómo se diferencian BFS y DFS y cómo usar el arreglo visitado en Python para no repetir nodos.

9.1 ¿Qué es un recorrido?

Es un proceso sistemático que visita vértices a partir de uno o más nodos iniciales, siguiendo las aristas del grafo y marcando los ya procesados para evitar repeticiones. Igual que en árboles binarios, donde existen tres recorridos clásicos (preorden, inorden y postorden), en grafos hay dos formas principales de explorar: por anchura (BFS) y por profundidad (DFS).

9.2 Importancia y usos de los recorridos

  • Detectar conectividad y componentes.
  • Encontrar rutas y calcular distancias (BFS en grafos no ponderados).
  • Detectar ciclos u ordenar tareas (DFS para topológico en digrafos acíclicos).
  • Preparar estructuras previas a algoritmos de caminos mínimos o flujos.

9.3 Diferencias BFS/DFS

  • BFS: (breadth-first search - búsqueda en anchura) usa una cola, visita por capas y encuentra distancias mínimas en aristas sin peso.
    Abrir visualizador BFS interactivo
  • DFS: (depth-first search - búsqueda en profundidad) usa pila (implícita con recursión o explícita), profundiza antes de retroceder y es útil para detectar ciclos y tiempos de entrada/salida.
    Abrir visualizador DFS interactivo

9.4 Requisitos y estructuras auxiliares

Se necesita una estructura de grafo (matriz o lista), una cola o pila según el recorrido, y un arreglo visitado para marcar vértices ya explorados.

9.5 Preparación del arreglo visitado

Se inicializa en False para todos los vértices. Al visitar uno, se marca en True. En grafos no dirigidos evita bucles infinitos; en dirigidos permite seguir las aristas con dirección correcta sin repetir nodos.

9.6 Recorridos en grafos dirigidos y no dirigidos

En grafos no dirigidos, las aristas se recorren en ambos sentidos; el marcado con visitado evita volver por el mismo borde. En digrafos, solo se siguen aristas en su sentido; BFS y DFS se aplican igual, pero el resultado respeta la orientación.

from collections import deque

def bfs(g, origen):
  if origen not in g:
    return
  visitado = {v: False for v in g}
  cola = deque([origen])
  visitado[origen] = True

  while cola:
    u = cola.popleft()
    print(u, end=" ")
    for v, _ in g[u]:
      if not visitado[v]:
        visitado[v] = True
        cola.append(v)
def dfs(g, origen):
  if origen not in g:
    return
  visitado = {v: False for v in g}
  dfs_rec(g, origen, visitado)

def dfs_rec(g, u, visitado):
  visitado[u] = True
  print(u, end=" ")
  for v, _ in g[u]:
    if not visitado[v]:
      dfs_rec(g, v, visitado)

Para grafos con varios componentes, inicia BFS/DFS desde cada vértice no visitado hasta cubrirlos todos. Así garantizas que el marcado visitado abarque el grafo completo.

Retornar