14 - Árboles generados por recorridos

Al recorrer un grafo, cada vez que avanzamos a un nodo nuevo creamos una arista “de árbol”. Estas aristas forman un subgrafo sin ciclos que captura cómo alcanzamos cada vértice: el árbol de recorrido. Guardarlo permite reconstruir caminos, calcular niveles y clasificar el resto de las aristas.

14.1 Árbol BFS

El árbol BFS se genera tomando la primera vez que llegamos a cada nodo desde la cola. Sus propiedades clave:

• Las aristas del árbol conectan nodos con niveles consecutivos (distancia mínima en aristas desde la raíz).
• Cada nodo guarda su padre y su nivel; reconstruir el camino mínimo es retroceder por padres hasta la raíz.
• En grafos no ponderados, el árbol BFS entrega las distancias mínimas en cantidad de aristas.

Abrir generador de árbol BFS

14.2 Árbol DFS

El árbol DFS se arma siguiendo aristas de árbol en el orden de profundización. Diferencias respecto de BFS:

• La profundidad no representa distancia mínima, sino el orden en que se descendieron las llamadas recursivas.
• Las aristas que no forman parte del árbol pueden ser de retroceso, avance o cruce; se detectan con tiempos de entrada/salida.
• Es la base para detección de ciclos, orden topológico y Tarjan.

Abrir generador de árbol DFS

14.3 Vector padre

El vector padre guarda para cada vértice el nodo desde el cual fue descubierto. Se inicializa en -1 o None y se completa al marcar visitados. Usos típicos:

• Reconstruir caminos y niveles sin volver a recorrer el grafo.
• Construir explícitamente el árbol (lista de aristas padre-hijo).
• Detectar ciclos en no dirigidos evitando contar la arista al padre.

14.4 Clasificación de aristas

Con los tiempos de descubrimiento (tin) y finalización (tout) del DFS podemos clasificar:

• Tree edge: lleva a un nodo no visitado; forma parte del árbol DFS.
• Back edge: apunta a un ancestro en la pila; indica ciclo.
• Forward edge: va a un descendiente ya finalizado (solo en dirigidos).
• Cross edge: conecta subárboles distintos o niveles sin relación directa.

14.5 Aplicaciones prácticas

• Reconstruir rutas y distancias en navegación GPS o saltos mínimos de red usando el árbol BFS.
• Encontrar ciclos, puentes y puntos de articulación a partir del árbol DFS y la clasificación de aristas.
• Generar orden topológico y detectar dependencias imposibles en digrafos.
• Reducir el grafo a su árbol de expansión para visualizaciones o simulaciones más livianas.

Implementación en Python

Dos programas completos y separados para probar directamente en VSCode. Ambos usan listas de adyacencia sin dependencias externas.

Arma el árbol BFS (programa completo)

from collections import deque

def agregar_arista(g, u, v):
  g[u].append((v, 1))
  g[v].append((u, 1))

def imprimir_arbol_bfs(g, origen):
  padre = {v: None for v in g}
  nivel = {v: -1 for v in g}
  cola = deque([origen])
  padre[origen] = origen
  nivel[origen] = 0

  print(f"Arbol BFS (origen {origen}):")
  while cola:
    u = cola.popleft()
    for v, _ in g[u]:
      if padre[v] is None:
        padre[v] = u
        nivel[v] = nivel[u] + 1
        print(f"{u} -- {v} (nivel {nivel[v]})")
        cola.append(v)

def main():
  g = {i: [] for i in range(6)}
  agregar_arista(g, 0, 1)
  agregar_arista(g, 0, 2)
  agregar_arista(g, 1, 3)
  agregar_arista(g, 1, 4)
  agregar_arista(g, 2, 5)

  imprimir_arbol_bfs(g, 0)

if __name__ == "__main__":
  main()

Arma el árbol DFS (programa completo)

def agregar_arista(g, u, v):
  g[u].append((v, 1))
  g[v].append((u, 1))

def dfs_arbol(g, u, padre, nivel, visitado):
  visitado[u] = True
  if padre is not None:
    print(f"{padre} -- {u} (nivel {nivel})")
  for v, _ in g[u]:
    if not visitado[v]:
      dfs_arbol(g, v, u, nivel + 1, visitado)

def main():
  g = {i: [] for i in range(6)}
  agregar_arista(g, 0, 1)
  agregar_arista(g, 0, 2)
  agregar_arista(g, 1, 3)
  agregar_arista(g, 1, 4)
  agregar_arista(g, 2, 5)

  visitado = {v: False for v in g}
  print("Arbol DFS (origen 0):")
  dfs_arbol(g, 0, None, 0, visitado)

if __name__ == "__main__":
  main()