Algoritmos de Grafos Esenciales para Entrevistas de Programación

1. Cómo Identificar un Problema de Grafos Oculto

Durante una entrevista en una gran empresa tecnológica, rara vez recibes un enunciado que diga explícitamente: "Aquí hay un grafo acíclico dirigido, por favor recórrelo". En cambio, los problemas de grafos suelen disfrazarse de escenarios del mundo real o rompecabezas basados en cuadrículas.

Deberías empezar a pensar en algoritmos de grafos inmediatamente si la descripción del problema involucra alguno de los siguientes temas:

• Conexiones: "Encuentra personas que son amigos de amigos", "Determina si hay un vuelo entre la Ciudad A y la Ciudad B".
• Dependencias: "Tienes una lista de tareas y requisitos previos, ¿en qué orden deberías completarlas?" o "Compilar un proyecto con dependencias".
• Cuadrículas y Laberintos: "Encuentra el camino más corto para salir de este laberinto de matriz 2D", "Cuenta el número de islas en una cuadrícula".
• Transformaciones: "Cambia una palabra por otra palabra cambiando una sola letra a la vez (Word Ladder)".

Una vez que identificas el problema como un problema de grafos, tu siguiente paso es descubrir la mejor representación. Las Listas de Adyacencia (usando Hash Maps o Listas de Listas) son generalmente la mejor opción para entornos de entrevistas porque son eficientes en memoria y rápidas de iterar. Las cuadrículas (matrices 2D) actúan como grafos implícitos, donde cada celda es un nodo y sus celdas adyacentes son sus aristas.

2. Patrón 1: Búsqueda en Anchura (BFS) para Caminos Más Cortos

La Búsqueda en Anchura es tu algoritmo de referencia siempre que un problema pregunte por el "camino más corto" o el "número mínimo de pasos" en un grafo no ponderado.

BFS explora el grafo nivel por nivel, irradiando hacia afuera como ondas en un estanque. Debido a que explora todos los nodos a una distancia de 1 antes de explorar cualquier nodo a una distancia de 2, la primera vez que alcanza el nodo de destino, se garantiza que ha encontrado el camino más corto.

Palabras Clave de Identificación:

Camino más corto, pasos mínimos, más cercano, recorrido por niveles.

Patrón de Implementación (Python):

BFS siempre requiere una Cola (Queue) (estructura de datos FIFO) y un Conjunto de Visitados (Visited Set) para evitar bucles infinitos.

from collections import deque

def bfs_shortest_path(graph, start, target):
    queue = deque([(start, 0)]) # (current_node, distance)
    visited = set([start])
    
    while queue:
        node, distance = queue.popleft()
        
        if node == target:
            return distance
            
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, distance + 1))
                
    return -1 # Camino no encontrado

Problemas Clásicos de LeetCode: Word Ladder, Shortest Path in Binary Matrix, Rotting Oranges.

3. Patrón 2: Búsqueda en Profundidad (DFS) para Conectividad

La Búsqueda en Profundidad explora un grafo yendo tan profundo como sea posible por un camino antes de retroceder (backtracking). Si bien rara vez se usa para encontrar el camino más corto, es increíblemente eficiente para explorar toda la estructura de un grafo, encontrar componentes o verificar si existe algún camino.

DFS es muy favorecido en las entrevistas porque se puede implementar de manera muy concisa usando recursividad.

Palabras Clave de Identificación:

Conectividad, alcanzabilidad, todos los caminos, explorar regiones, backtracking, búsqueda profunda.

Patrón de Implementación (Python):

DFS requiere una Pila (Stack) (LIFO), que se maneja más comúnmente de forma implícita mediante la pila de llamadas a través de la recursividad.

def dfs_traverse(graph, start, visited=None):
    if visited is None:
        visited = set()
        
    visited.add(start)
    # Procesa el nodo aquí
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_traverse(graph, neighbor, visited)
            
    return visited

Nota: Si estás haciendo backtracking (como encontrar todos los caminos válidos o permutaciones), necesitarás eliminar el nodo del conjunto `visited` después de que la llamada recursiva regrese.

Problemas Clásicos de LeetCode: Number of Islands, Clone Graph, Pacific Atlantic Water Flow.

4. Patrón 3: Ordenamiento Topológico para Dependencias

Si un problema te pide que ordenes elementos en función de requisitos previos, necesitas el Ordenamiento Topológico. Este algoritmo solo funciona en Grafos Acíclicos Dirigidos (DAGs). Si hay un ciclo (por ejemplo, la Tarea A requiere la Tarea B, y la Tarea B requiere la Tarea A), el ordenamiento topológico es imposible.

La forma más intuitiva de implementar esto en una entrevista es utilizando el Algoritmo de Kahn, que se basa en calcular el "grado de entrada" (in-degree, número de aristas entrantes) de cada nodo.

Palabras Clave de Identificación:

Requisitos previos, dependencias, programación, ordenamiento, compilación, resolución.

Patrón de Implementación (Python):

from collections import deque, defaultdict

def topological_sort(num_courses, prerequisites):
    # 1. Construir el Grafo y el arreglo de Grado de Entrada
    graph = defaultdict(list)
    in_degree = {i: 0 for i in range(num_courses)}
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
        
    # 2. Encontrar todos los nodos con grado de entrada 0 (sin requisitos previos)
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    top_order = []
    
    # 3. Procesar la cola
    while queue:
        node = queue.popleft()
        top_order.append(node)
        
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
                
    # 4. Comprobar si hay ciclos
    if len(top_order) == num_courses:
        return top_order
    return [] # Ciclo detectado

Problemas Clásicos de LeetCode: Course Schedule I & II, Alien Dictionary.

5. Patrón 4: Union-Find (Conjuntos Disjuntos) para Componentes Conexas

Union-Find es una estructura de datos especializada que se usa específicamente para rastrear la partición de un conjunto en subconjuntos disjuntos. Responde a dos preguntas de forma asombrosamente rápida (en un tiempo cercano a O(1)):

1. ¿Están el Nodo A y el Nodo B en la misma componente?
2. ¿Podemos fusionar la componente que contiene al Nodo A con la componente que contiene al Nodo B?

Es la herramienta perfecta para encontrar ciclos en grafos no dirigidos o agrupar elementos dinámicamente.

Palabras Clave de Identificación:

Componentes conexas, conectividad dinámica, agrupamiento, conexión redundante, fusionar conjuntos.

Patrón de Implementación (Python):

Debes memorizar la implementación de una clase Union-Find, recordando específicamente incluir la Compresión de Caminos (Path Compression) en el método `find` para garantizar una complejidad de tiempo óptima.

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [1] * size

    def find(self, x):
        # Compresión de caminos
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x == root_y:
            return False # Ya están en el mismo conjunto (ciclo detectado)
            
        # Union by rank (Unión por rango)
        if self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        elif self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
            
        return True

Problemas Clásicos de LeetCode: Redundant Connection, Number of Connected Components in an Undirected Graph, Accounts Merge.

6. Patrón 5: Dijkstra para el Camino Más Corto Ponderado

Si el problema pide el camino más corto, pero las aristas tienen pesos (costos, tiempos, distancias), la búsqueda BFS estándar fallará. Necesitas el algoritmo de Dijkstra.

Dijkstra es esencialmente BFS, pero en lugar de una Cola estándar, utiliza una Cola de Prioridad (Min-Heap) para garantizar que siempre se explore el camino más barato disponible a continuación.

Palabras Clave de Identificación:

Camino más corto con costos, vuelo más barato, tiempo mínimo, retraso de red.

Patrón de Implementación (Python):

import heapq

def dijkstra(graph, start, target):
    # La cola de prioridad almacena tuplas de (total_cost, node)
    pq = [(0, start)]
    # Diccionario para mantener un registro del costo mínimo para llegar a cada nodo
    min_cost = {start: 0}
    
    while pq:
        current_cost, node = heapq.heappop(pq)
        
        # Si llegamos al objetivo, se garantiza que este es el camino más corto
        if node == target:
            return current_cost
            
        # Si encontramos un camino más corto anteriormente, ignora esta tupla antigua
        if current_cost > min_cost.get(node, float('inf')):
            continue
            
        for neighbor, weight in graph[node]:
            new_cost = current_cost + weight
            
            # Solo enviar a la cola si encontramos un camino estrictamente mejor
            if new_cost < min_cost.get(neighbor, float('inf')):
                min_cost[neighbor] = new_cost
                heapq.heappush(pq, (new_cost, neighbor))
                
    return -1

Problemas Clásicos de LeetCode: Network Delay Time, Cheapest Flights Within K Stops (Nota: Bellman-Ford también es bueno para esto), Path With Maximum Probability.