Algoritmos de Matrices y Grafos en Python: Guía Completa con Ejemplos Prácticos

1. Fundamentos de Matrices

Una matriz es una tabla de valores numéricos que permite representar datos estructurados y operaciones lineales. En Python, la herramienta de referencia es NumPy, que brinda vectores y matrices multidimensionales altamente optimizadas en C.

1.1. Operaciones esenciales

• np.dot o el operador @: multiplicación de matrices.
• np.linalg.inv: inversa de una matriz cuadrada.
• np.linalg.eig: valores y vectores propios.

1.2. Ejemplo: Multiplicación de matrices (O(n³) clásico)

import numpy as np

def multiplicar_matrices(A, B):
    """Multiplica dos matrices cuadradas usando NumPy (optimizado en C)."""
    return A @ B

# Matrices de ejemplo 3x3
A = np.array([[1, 2, 3],
              [4, 5, 6],
              [7, 8, 9]])
B = np.array([[9, 8, 7],
              [6, 5, 4],
              [3, 2, 1]])

C = multiplicar_matrices(A, B)
print(C)

Resultado:

[[ 30  24  18]
 [ 84  69  54]
 [138 114  90]]

2. Fundamentos de Grafos

Un grafo está compuesto por un conjunto de vértices (nodos) y aristas (conexiones). Los grafos pueden representarse mediante matrices de adyacencia o listas de adyacencia. Cada representación tiene ventajas y desventajas en términos de complejidad espacial y temporal.

2.1. Biblioteca recomendada: NetworkX

NetworkX es la librería estándar para crear, manipular y analizar grafos en Python. Ofrece estructuras internas basadas en diccionarios que combinan la flexibilidad de la lista de adyacencia con una API intuitiva.

2.2. Ejemplo: Creación y visualización de un grafo simple

import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()  # Grafo dirigido
G.add_edge('A', 'B', weight=3)
G.add_edge('A', 'C', weight=5)
G.add_edge('B', 'C', weight=2)
G.add_edge('C', 'A', weight=4)

pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color='gray')
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.title('Grafo dirigido con pesos')
plt.show()

3. Algoritmos Clásicos sobre Grafos

En esta sección cubrimos dos algoritmos fundamentales: Floyd‑Warshall (todos los pares más cortos) y BFS/DFS (búsqueda en anchura y profundidad). Cada uno se implementa tanto con matrices como con listas de adyacencia para comparar rendimiento.

3.1. Floyd‑Warshall (O(V³))

import numpy as np

def floyd_warshall(adj):
    """Devuelve la matriz de distancias mínimas usando Floyd‑Warshall.
    adj: matriz de adyacencia donde INF representa ausencia de arista.
    """
    n = adj.shape[0]
    dist = adj.copy()
    for k in range(n):
        # broadcasting permite actualizar toda la matriz en una sola operación vectorizada
        dist = np.minimum(dist, dist[:, k, None] + dist[None, k, :])
    return dist

INF = 1e9
A = np.array([[0,   3, INF,   7],
              [8,   0,   2, INF],
              [5, INF,   0,   1],
              [2, INF, INF,   0]], dtype=float)

print(floyd_warshall(A))

Resultado (distancias mínimas):

[[0. 3. 5. 6.]
 [5. 0. 2. 3.]
 [3. 6. 0. 1.]
 [2. 5. 7. 0.]]

3.2. BFS y DFS con lista de adyacencia

from collections import deque

def bfs(graph, start):
    visited = set()
    order = []
    q = deque([start])
    while q:
        v = q.popleft()
        if v in visited:
            continue
        visited.add(v)
        order.append(v)
        q.extend(neigh for neigh in graph[v] if neigh not in visited)
    return order

def dfs(graph, start, visited=None, order=None):
    if visited is None:
        visited = set()
    if order is None:
        order = []
    visited.add(start)
    order.append(start)
    for neigh in graph[start]:
        if neigh not in visited:
            dfs(graph, neigh, visited, order)
    return order

# Grafo como lista de adyacencia (diccionario)
G = {
    'A': ['B', 'C'],
    'B': ['C', 'D'],
    'C': ['D'],
    'D': []
}

print('BFS:', bfs(G, 'A'))
print('DFS:', dfs(G, 'A'))

Salida:

BFS: ['A', 'B', 'C', 'D']
DFS: ['A', 'B', 'C', 'D']

4. Comparativa de Rendimiento y Escalabilidad

El siguiente cuadro muestra el comportamiento típico de los algoritmos presentados según la densidad del grafo y el tamaño de la matriz.

Tip de optimización: Cuando trabajas con matrices extremadamente grandes (>10⁴×10⁴), considera SciPy.sparse para almacenar sólo los valores no nulos y usar algoritmos de sparse matrix multiplication o shortest path adaptados.

5. Troubleshooting, Seguridad y Buenas Prácticas

5.1. Errores comunes

• Dimensiones incompatibles: NumPy lanza ValueError: shapes (m,n) and (p,q) not aligned. Verifica que n == p.
• Overflow en enteros: Usa dtype np.int64 o np.float64 para evitar wrap‑around.
• Grafos desconectados en Floyd‑Warshall: Representa la ausencia de arista con un valor INF suficientemente grande (p. ej., 1e12) para que no afecte a la suma.

5.2. Seguridad

Al procesar datos externos (p. ej., archivos CSV con matrices), valida siempre el número de columnas y filas antes de convertir a np.array. Esto previene ataques de denegación de servicio mediante matrices gigantes que agoten la memoria.

5.3. Mejores prácticas de rendimiento

• Prefiere operaciones vectorizadas de NumPy sobre bucles Python.
• Utiliza numba o Cython para kernels críticos que no estén cubiertos por BLAS.
• Para grafos muy grandes, emplea igraph o graph-tool, que están escritos en C++ y ofrecen mejor escalabilidad.

Conclusión

Los algoritmos basados en matrices y grafos siguen siendo la columna vertebral de innumerables aplicaciones: desde la optimización de rutas en logística hasta el entrenamiento de redes neuronales. Dominar NumPy y NetworkX, conocer cuándo usar matrices densas versus estructuras esparcidas, y aplicar buenas prácticas de rendimiento son habilidades esenciales para cualquier ingeniero de datos o desarrollador de backend.

¡Empieza a experimentar! Modifica los ejemplos, mide tiempos con timeit y escala tus soluciones a entornos de producción usando contenedores Docker para garantizar reproducibilidad.