0Pricing
DSA Interview Prep · Lección

Representaciones de grafos y preparación de recorridos

Construya grafos dirigidos y no dirigidos con listas de adyacencia, inicialice BFS con un deque y DFS con una pila o recursión, controlando los nodos visitados.

Representaciones de grafos y preparación de recorridos es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.

¿Qué es un grafo?

Un grafo es un conjunto de nodos (vértices) conectados mediante aristas. A diferencia de los árboles, los grafos pueden tener ciclos, varios caminos entre nodos y componentes desconectados. Los grafos modelan sistemas del mundo real, como redes sociales, mapas de carreteras, árboles de dependencias y enlaces entre páginas web. Casi todas las entrevistas de diseño de sistemas y algoritmos que no sean triviales abordan los grafos; dominar su representación y sus recorridos es esencial.

# Graph terminology:
# - V: set of vertices (nodes)
# - E: set of edges
# - Directed graph: edges have direction (A -> B but not B -> A)
# - Undirected graph: edges are bidirectional
# - Weighted graph: edges have costs/weights
# - Cyclic: contains at least one cycle
# - Acyclic: no cycles (DAG = Directed Acyclic Graph)
# - Connected: every node reachable from every other
# - Disconnected: multiple isolated components
print('Graph: nodes + edges, directed/undirected, weighted/unweighted')

Representación mediante lista de adyacencia

Una lista de adyacencia almacena la lista de vecinos de cada nodo. En Python, utilice un dict que asocie cada nodo con una lista de nodos adyacentes. Esta es la representación más común en los problemas de entrevistas: espacio O(V + E) (eficiente para grafos dispersos), O(grado) para recorrer los vecinos y O(1) en promedio para comprobar la adyacencia con una variante basada en un conjunto hash. La mayoría de los problemas de grafos de LeetCode utilizan este formato.

from collections import defaultdict

# Build an undirected graph
def build_undirected(edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)  # both directions
    return graph

edges = [(0,1), (0,2), (1,3), (2,3), (3,4)]
graph = build_undirected(edges)
print(dict(graph))
# {0:[1,2], 1:[0,3], 2:[0,3], 3:[1,2,4], 4:[3]}

# Directed graph: only one direction
def build_directed(edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)  # only u -> v
    return graph

Representación mediante matriz de adyacencia

Una matriz de adyacencia es un arreglo bidimensional V×V donde matrix[i][j] = 1 (o el peso de la arista) si existe una arista de i a j, y 0 en caso contrario. Permite consultar una arista en O(1), pero utiliza un espacio O(V²) independientemente del número de aristas, lo que resulta ineficiente para grafos dispersos. Se prefiere cuando el grafo es denso (tiene muchas aristas) o cuando es fundamental comprobar rápidamente la existencia de aristas, como en los caminos más cortos entre todos los pares de Floyd-Warshall.

# Adjacency matrix for 5 nodes
V = 5
matrix = [[0] * V for _ in range(V)]

edges = [(0,1), (0,2), (1,3), (2,3), (3,4)]
for u, v in edges:
    matrix[u][v] = 1
    matrix[v][u] = 1  # undirected

# Print the matrix:
for row in matrix:
    print(row)
# Neighbour check: O(1)
print('Edge 0-2:', bool(matrix[0][2]))  # True
print('Edge 0-4:', bool(matrix[0][4]))  # False

# Space: O(V^2) vs adjacency list O(V+E)
# Dense graph: matrix often better; sparse: list better

Representación mediante lista de aristas

Una lista de aristas es la representación más sencilla: solo una lista de tuplas (origen, destino), opcionalmente con pesos. Utiliza un espacio O(E) y permite recorrer fácilmente todas las aristas. Sin embargo, para encontrar los vecinos de un nodo es necesario examinar todas las aristas: O(E). Las listas de aristas se utilizan en algoritmos de grafos que recorren exhaustivamente todas las aristas, como Bellman-Ford (relajar todas las aristas n-1 veces) y el algoritmo de Kruskal para obtener el árbol de expansión mínima.

# Weighted edge list: (source, destination, weight)
edge_list = [
    (0, 1, 4),
    (0, 2, 1),
    (1, 3, 1),
    (2, 3, 5),
    (3, 4, 3)
]

# Useful for:
# Bellman-Ford: iterate all edges n-1 times
# Kruskal's MST: sort by weight then union-find

# Sort by weight for Kruskal:
edge_list_sorted = sorted(edge_list, key=lambda e: e[2])
print('Sorted by weight:', edge_list_sorted)

# Finding neighbours: O(E) scan -- inefficient for traversal
node_0_neighbors = [v for u, v, w in edge_list if u == 0]
print('Node 0 neighbors:', node_0_neighbors)

Configuración de BFS: cola y conjunto de visitados

BFS (búsqueda en anchura) explora un grafo nivel por nivel mediante una cola. El componente fundamental es un conjunto de visitados para evitar volver a visitar nodos en grafos cíclicos. Sin el conjunto de visitados, BFS recorrería un grafo cíclico indefinidamente. La configuración estándar consiste en inicializar la cola con el nodo de origen, marcarlo como visitado y, después, desencolar, procesar y encolar repetidamente los vecinos que aún no se hayan visitado.

from collections import deque

def bfs(graph, start):
    visited = {start}        # mark source as visited
    queue = deque([start])   # initialise queue
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)     # mark BEFORE enqueue
                queue.append(neighbour)
    return order

from collections import defaultdict
graph = defaultdict(list)
for u, v in [(0,1),(0,2),(1,3),(2,3),(3,4)]:
    graph[u].append(v); graph[v].append(u)

print(bfs(graph, 0))  # [0, 1, 2, 3, 4]

Configuración de DFS: pila o recursión

DFS (búsqueda en profundidad) explora cada rama lo más lejos posible antes de retroceder. Impleméntelo de forma recursiva (mediante la pila de llamadas) o iterativa (mediante una pila explícita). Ambas variantes requieren un conjunto de visitados para los grafos cíclicos. La versión iterativa inserta los vecinos en orden inverso para coincidir con el orden de recorrido del DFS recursivo, aunque el orden de exploración puede variar entre ambas implementaciones.

def dfs_recursive(graph, node, visited=None, order=None):
    if visited is None: visited = set(); order = []
    visited.add(node)
    order.append(node)
    for neighbour in graph[node]:
        if neighbour not in visited:
            dfs_recursive(graph, neighbour, visited, order)
    return order

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        if node in visited: continue
        visited.add(node)
        order.append(node)
        for neighbour in reversed(graph[node]):  # reverse for same order as recursive
            if neighbour not in visited:
                stack.append(neighbour)
    return order

print('Recursive DFS:', dfs_recursive(graph, 0))
print('Iterative DFS:', dfs_iterative(graph, 0))

Cuándo usar BFS frente a DFS

Elija BFS cuando necesite el camino más corto (el menor número de aristas) en un grafo no ponderado o cuando necesite procesar los nodos nivel por nivel. Elija DFS cuando necesite explorar todos los nodos alcanzables, detectar ciclos, encontrar componentes conexos, realizar una ordenación topológica o enumerar todos los caminos. En la práctica: BFS para «camino más corto/mínimo de saltos» y DFS para «existencia/accesibilidad/enumeración».

# BFS use cases:
# - Shortest path in unweighted graph (fewest edges)
# - Level-order traversal
# - Word ladder (minimum transformations)
# - Clone graph

# DFS use cases:
# - Connected components (flood fill)
# - Cycle detection
# - Topological sort
# - All paths between two nodes
# - Maze solving (any path)
# - N-queens, Sudoku (backtracking)

# Both: O(V + E) time, O(V) space for visited
print('BFS: shortest hops | DFS: existence and enumeration')

Grafos a partir de los formatos de entrada de LeetCode

Los problemas de grafos de LeetCode utilizan distintos formatos de entrada. Lista de aristas: [[0,1],[0,2]] — construya una lista de adyacencia. Lista de adyacencia basada en índices: graph[i] es la lista de vecinos de i. Cuadrícula o matriz: un arreglo bidimensional m×n donde las celdas son nodos y las celdas adyacentes (arriba/abajo/izquierda/derecha) son vecinas. Nodo con hijos: clases personalizadas como Node(val, neighbors). Reconozca estos formatos y conviértalos en una lista de adyacencia como primer paso.

# Format 1: edge list -> adjacency list
def edges_to_adj(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    return graph

# Format 2: 2D grid -> adjacency (implicit)
# Neighbours of (r, c): (r-1,c), (r+1,c), (r,c-1), (r,c+1)
DIRS = [(-1,0),(1,0),(0,-1),(0,1)]
def grid_neighbours(grid, r, c):
    rows, cols = len(grid), len(grid[0])
    return [(r+dr, c+dc) for dr, dc in DIRS
            if 0 <= r+dr < rows and 0 <= c+dc < cols]

grid = [[1,1,0],[0,1,1],[1,0,0]]
print('Neighbours of (0,0):', grid_neighbours(grid, 0, 0))
print('Neighbours of (1,1):', grid_neighbours(grid, 1, 1))

Marcar los visitados en cuadrículas

En los problemas de cuadrículas, hay dos formas de llevar el control de las celdas visitadas. Opción A: utilice un conjunto visited independiente de tuplas (row, col), con un espacio adicional O(m*n). Opción B: modifique la cuadrícula directamente marcando las celdas visitadas con un valor centinela (por ejemplo, '#' o 2) y restáurelas después si es necesario. El enfoque directo utiliza un espacio adicional O(1) y es habitual en los problemas de relleno por inundación y de número de islas.

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != '1':
            return
        grid[r][c] = '#'  # mark as visited (in-place)
        dfs(r+1, c); dfs(r-1, c)
        dfs(r, c+1); dfs(r, c-1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count

grid = [['1','1','0','0'],
        ['1','1','0','0'],
        ['0','0','1','0'],
        ['0','0','0','1']]
print(num_islands(grid))  # 3

Inicializar BFS con múltiples fuentes

BFS de múltiples fuentes comienza simultáneamente desde varios nodos mediante la inicialización de la cola con todos los nodos de origen marcados como visitados. Se utiliza en problemas como «distancia al 0 más cercano», «naranjas podridas» y «muros y puertas», donde se busca la distancia más corta desde cualquiera de los nodos de origen. El BFS de múltiples fuentes se ejecuta en O(V + E), igual que el de una sola fuente, porque cada nodo se visita como máximo una vez.

from collections import deque

def rotting_oranges(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    # Multi-source: all rotten oranges start at time=0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))  # (row, col, time)
            elif grid[r][c] == 1:
                fresh += 1
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
    time = 0
    while queue:
        r, c, t = queue.popleft()
        for dr, dc in dirs:
            nr, nc = r+dr, c+dc
            if 0<=nr<rows and 0<=nc<cols and grid[nr][nc]==1:
                grid[nr][nc] = 2  # mark rotten
                fresh -= 1
                queue.append((nr, nc, t+1))
                time = t + 1
    return time if fresh == 0 else -1

print(rotting_oranges([[2,1,1],[1,1,0],[0,1,1]]))  # 4

Densidad del grafo y elección de la representación

La elección entre una lista y una matriz de adyacencia depende de la densidad del grafo, es decir, de la proporción E/V². Un grafo disperso (E << V²) se beneficia de las listas de adyacencia: espacio O(V+E) frente a O(V²) para una matriz. Un grafo denso (E ≈ V²) se beneficia de las matrices de adyacencia: consulta de aristas en O(1) frente a O(grado) con listas. En los problemas de entrevistas, las listas de adyacencia casi siempre son la opción correcta, ya que la mayoría de los problemas involucran grafos dispersos.

# Graph density comparison:
# Sparse: social network (V=1B users, avg 200 friends)
#   E = 200 * 1B = 200B << V^2 = 10^18 -> adjacency list
# Dense: complete graph (every node connected to every other)
#   E = V*(V-1)/2 ≈ V^2 -> adjacency matrix

# Interview rule of thumb:
# - Default to adjacency list (defaultdict(list))
# - Use matrix only when asked about dense graph or O(1) edge lookup
# - Grid problems: use implicit adjacency (4-directional neighbours)

print('Sparse graph (E << V^2): use adjacency list')
print('Dense graph (E ~ V^2): consider adjacency matrix')

Comprobación rápida

Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

Resumen de la lección

En esta lección ha aprendido: tres representaciones de grafos (lista de adyacencia, matriz y lista de aristas) y cuándo elegir cada una, la configuración de BFS y DFS con conjuntos de visitados para evitar bucles infinitos en grafos cíclicos, y patrones prácticos como el marcado directo de cuadrículas y el BFS de múltiples fuentes. A continuación, aplicará BFS para encontrar caminos más cortos y realizar recorridos por niveles.

Preguntas frecuentes

¿La lección «Representaciones de grafos y preparación de recorridos» es gratis?

Sí — el texto completo de «Representaciones de grafos y preparación de recorridos» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.

¿Qué aprenderé en «Representaciones de grafos y preparación de recorridos»?

Construya grafos dirigidos y no dirigidos con listas de adyacencia, inicialice BFS con un deque y DFS con una pila o recursión, controlando los nodos visitados. Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar DSA Interview Prep?

No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.

¿Cuánto tiempo toma la lección «Representaciones de grafos y preparación de recorridos»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?

Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

  1. Representaciones de grafos y preparación de recorridos
  2. BFS: ruta más corta y recorrido por niveles
  3. DFS: componentes conexos y flood fill
  4. Detección de ciclos en grafos dirigidos y no dirigidos
← Volver a DSA Interview Prep