Posgrado → Personalización → Optimización Combinatoria ↓
Algoritmos de grafos
Los grafos son estructuras matemáticas utilizadas para modelar relaciones emparejadas entre objetos. Un grafo en este contexto está compuesto por vértices (también llamados nodos o puntos) que están conectados por aristas (también llamadas enlaces o líneas). Los algoritmos de grafos son procedimientos matemáticos diseñados para resolver problemas que involucran grafos.
Importancia de los algoritmos de grafos
Los grafos son fundamentalmente importantes en muchos campos, incluyendo la informática, la biología y las ciencias sociales. Ayudan a resolver problemas como el flujo de redes, encontrar caminos más cortos, crear árboles de expansión, y mucho más. Vamos a explorar algunos algoritmos básicos y avanzados de grafos.
Definiciones básicas
Antes de adentrarnos en los algoritmos, es esencial entender algunos términos básicos relacionados con los grafos.
- Vértice (o nodo): El punto en un grafo donde las aristas se encuentran.
- Arista (o enlace): Una conexión entre dos vértices.
- Adyacencia: Dos vértices son adyacentes si están directamente conectados por una arista.
- Camino: Una secuencia de aristas que conecta una secuencia de vértices.
- Ciclo: Un camino que comienza y termina en el mismo vértice.
- Grafo conectado: Un grafo en el que hay un camino entre cada par de vértices.
Tipos de grafos
- Grafo dirigido (digrafo): Un grafo en el que las aristas tienen direcciones. Cada arista es un par ordenado de vértices.
- Grafo no dirigido: Un grafo en el que las aristas no tienen dirección. Cada arista es un par no ordenado de vértices.
- Grafo ponderado: Un grafo en el que cada arista tiene un valor numérico (peso) asociado.
- Grafo no ponderado: Un grafo en el que las aristas no tienen pesos.
- Grafo completo: Un grafo en el que hay exactamente una arista entre cada par de vértices.
Representación de grafos
Los grafos pueden representarse de dos maneras principales:
Matriz de adyacencia
La matriz de adyacencia es un arreglo 2D donde cada elemento indica si hay una arista entre pares de vértices.
a = [
[0, 1, 0, 0],
[1, 0, 1, 1],
[0, 1, 0, 1],
[0, 1, 1, 0]
]
Esta matriz muestra un grafo con 4 vértices y aristas entre los pares (0,1), (1,2), (1,3) y (2,3).
Lista de adyacencia
La lista de adyacencia representa el grafo como una lista de vértices, donde cada vértice tiene su propia lista de vértices adyacentes.
{
0: [1],
1: [0, 2, 3],
2: [1, 3],
3: [1, 2]
}
En esta lista, el vértice 0 está conectado al vértice 1, el vértice 1 está conectado a los vértices 0, 2, 3, y así sucesivamente.
Algoritmos de recorrido de grafos
El recorrido de grafos significa el proceso de visitar cada vértice de un grafo. Hay dos formas principales de recorrer un grafo:
Búsqueda en anchura (BFS)
BFS es un método que itera a través de un grafo explorando los nodos vecinos situados en la profundidad actual antes de pasar a los nodos situados en el siguiente nivel de profundidad.
def bfs(graph, start):
visited = set()
queue = [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(set(graph[vertex]) - visited)
return visited
En el código anterior, se recorre un grafo comenzando desde el vértice start. El método BFS utiliza una cola para llevar un registro de los puntos de vértice que se visitarán a continuación.
Ejemplo de BFS en acción
El anterior SVG muestra un grafo simple con vértices numerados del 0 al 3. Comenzando desde el vértice 0, BFS visitará nodos en este orden: 0, 1, 3, 2.
Búsqueda en profundidad (DFS)
DFS es un método de recorrido en el que se prioriza la profundidad, y se avanza lo más lejos posible a lo largo de una rama antes de retroceder.
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for next in graph[start]:
if next not in visited:
dfs(graph, next, visited)
return visited
En el código de DFS, el método se llama recursivamente y la pila se utiliza a través de las llamadas a la función para llevar un registro del camino.
Ejemplo de DFS en acción
Para el mismo grafo, DFS visitará los nodos en este orden: 0, 1, 2, 3.
Algoritmo de camino más corto
El objetivo de los algoritmos de grafos es a menudo encontrar el camino más corto entre nodos. Aquí están dos algoritmos de camino más corto bien conocidos:
Algoritmo de Dijkstra
El algoritmo de Dijkstra encuentra el camino más corto desde el vértice inicial a todos los demás vértices en un grafo ponderado.
import heapq
def dijkstra(graph, start):
queue = []
heapq.heappush(queue, (0, start))
distances = {node: float('infinity') for node in graph}
distances[start] = 0
while queue:
current_distance, current_node = heapq.heappop(queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
Este algoritmo mantiene una cola para encontrar las aristas con el menor peso acumulado primero. Utiliza una cola de prioridad (montículo mínimo) para obtener eficientemente la arista con la distancia mínima.
Algoritmo de Bellman-Ford
El algoritmo de Bellman-Ford calcula los caminos más cortos desde un solo vértice fuente a todos los demás vértices en un grafo. Puede manejar grafos con pesos negativos.
def bellman_ford(graph, start):
distance = {i: float('inf') for i in graph}
distance[start] = 0
for _ in range(len(graph) - 1):
for vertex in graph:
for neighbor, weight in graph[vertex].items():
if distance[vertex] + weight < distance[neighbor]:
distance[neighbor] = distance[vertex] + weight
for vertex in graph:
for neighbor, weight in graph[vertex].items():
if distance[vertex] + weight < distance[neighbor]:
raise ValueError("El grafo contiene un ciclo de peso negativo")
return distance
A diferencia del algoritmo de Dijkstra, Bellman-Ford funciona bien con grafos que contienen aristas con pesos negativos. Verifica repetidamente cada arista para asegurar que se hayan encontrado caminos óptimos.
Algoritmo de árbol de expansión mínimo (MST)
El árbol de expansión mínimo de un grafo conectado y no dirigido es un subconjunto de aristas que conecta todos los vértices sin ningún ciclo y con el peso total mínimo posible.
Algoritmo de Kruskal
El algoritmo de Kruskal construye el MST agregando aristas una por una, comenzando por la más corta, y agregando solo aquellas que no forman ciclos.
def kruskal(graph):
parent = {}
def find(n):
while parent[n] != n:
n = parent[n]
return n
def union(n1, n2):
root1 = find(n1)
root2 = find(n2)
parent[root2] = root1
graph.sort(key=lambda x: x[2])
for n1, n2, _ in graph:
parent[n1] = n1
parent[n2] = n2
mst = []
for n1, n2, weight in graph:
if find(n1) != find(n2):
union(n1, n2)
mst.append((n1, n2, weight))
return mst
Este algoritmo comienza ordenando todas las aristas por peso. Utiliza una estructura de datos de unión-búsqueda para llevar un registro de los componentes conectados y asegura que no se formen ciclos.
Algoritmo de Prim
El algoritmo de Prim construye un MST comenzando desde un vértice arbitrario y agregando sucesivamente la arista de menor peso desde los vértices ya seleccionados a los vértices no seleccionados.
import heapq
def prim(graph, start):
mst = []
visited = set()
min_edges = [(0, start, None)]
while min_edges:
weight, vertex, frm = heapq.heappop(min_edges)
if vertex in visited:
continue
visited.add(vertex)
if frm is not None:
mst.append((frm, vertex, weight))
for next_vertex, next_weight in graph[vertex].items():
if next_vertex not in visited:
heapq.heappush(min_edges, (next_weight, next_vertex, vertex))
return mst
El algoritmo de Prim utiliza una cola de prioridad para expandir siempre el nodo en la frontera actual con el menor costo.
Conclusión
Los algoritmos de grafos proporcionan soluciones a una amplia gama de problemas relacionados con redes de nodos y aristas. Ya sea encontrar el camino más corto, conexiones óptimas o recorrer nodos, estos algoritmos desempeñan un papel vital en la resolución eficiente de problemas complejos. Entender las definiciones básicas, las representaciones y los principales algoritmos como BFS, DFS, Dijkstra, Bellman-Ford, Kruskal y Prim es crucial para aprovechar los algoritmos de grafos en aplicaciones de la vida real.
Comentarios