Data Structure & Algorithms
Fundamentos de grafos, adjacency lists, matrices y edge lists, además de recorridos BFS y DFS en grafos dirigidos, ponderados o desconectados.
Un graph modela entidades y las relaciones que existen entre ellas. Los vértices representan elementos; las aristas representan conexiones.
A diferencia de una lista, un grafo no impone una secuencia. A diferencia de un árbol, no necesita raíz, puede tener ciclos y un vértice puede alcanzarse por varios caminos.
usuario ─sigue→ usuario
ciudad ─carretera→ ciudad
curso ─requiere→ curso
servidor ─conecta→ servidorLa primera decisión importante no es qué traversal usar. Es cómo representar el grafo y qué significan sus aristas.
V².En un grafo no dirigido, una arista conecta ambos sentidos:
A ─── BEn un grafo dirigido, la relación tiene orientación:
A ───→ BA → B no implica B → A. Guardar ambas direcciones por costumbre cambia el problema.
Una arista puede incluir distancia, tiempo, precio, capacidad o cualquier costo.
A ──4──→ BEl significado del peso determina qué algoritmos son válidos. Por ejemplo, Dijkstra requiere pesos no negativos.
Antes de implementar, define si permites:
Usar Set como vecinos elimina duplicados. Usar un array los conserva. Ninguna elección es universalmente correcta: depende del modelo.
Una matriz V × V guarda una celda por pareja de vértices.
| A | B | C | |
|---|---|---|---|
| A | 0 | 1 | 1 |
| B | 1 | 0 | 0 |
| C | 1 | 0 | 0 |
Ventajas:
O(1);Costos:
O(V²), incluso con pocas aristas;O(V).Cada vértice guarda sus vecinos:
A → B, C
B → A
C → AO(V + E);u: O(degree(u));O(degree(u)) con array o promedio O(1) con Set.Es la representación habitual para grafos dispersos.
Una lista de aristas guarda registros como:
type Edge<T> = {
from: T;
to: T;
weight?: number;
};Es útil cuando el algoritmo procesa aristas globalmente, como Bellman-Ford o Kruskal. Consultar vecinos directamente es costoso si no construyes un índice adicional.
class Graph<T> {
private readonly adjacency = new Map<T, Set<T>>();
constructor(private readonly directed = false) {}
addVertex(vertex: T): void {
if (!this.adjacency.has(vertex)) {
this.adjacency.set(vertex, new Set());
}
}
addEdge(from: T, to: T): void {
this.addVertex(from);
this.addVertex(to);
this.adjacency.get(from)!.add(to);
if (!this.directed) {
this.adjacency.get(to)!.add(from);
}
}
hasVertex(vertex: T): boolean {
return this.adjacency.has(vertex);
}
hasEdge(from: T, to: T): boolean {
return this.adjacency.get(from)?.has(to) ?? false;
}
neighbors(vertex: T): ReadonlySet<T> {
return this.adjacency.get(vertex) ?? new Set<T>();
}
vertices(): IterableIterator<T> {
return this.adjacency.keys();
}
}Esta implementación evita aristas duplicadas mediante Set. Para un weighted graph, los vecinos necesitarían almacenar también el peso, por ejemplo Map<T, number>.
Una estructura de producción tendría que definir eliminación, validación, serialización, igualdad de claves y política para actualizar pesos.
Breadth-First Search visita primero los vértices a una arista de distancia, luego los que están a dos, y así sucesivamente.
graph TD
A --> B
A --> C
B --> D
B --> E
C --> FDesde A, un orden posible es:
A → B → C → D → E → Ffunction bfs<T>(graph: Graph<T>, start: T): T[] {
if (!graph.hasVertex(start)) return [];
const visited = new Set<T>([start]);
const queue: T[] = [start];
const order: T[] = [];
let head = 0;
while (head < queue.length) {
const vertex = queue[head];
head += 1;
order.push(vertex);
for (const neighbor of graph.neighbors(vertex)) {
if (visited.has(neighbor)) continue;
visited.add(neighbor);
queue.push(neighbor);
}
}
return order;
}Array.shift() puede desplazar todos los elementos restantes y costar O(n). El índice head conserva el comportamiento FIFO sin mover el array.
Cuando un vértice sale de la cola, todos los vértices descubiertos antes tienen una distancia en cantidad de aristas menor o igual.
Depth-First Search sigue un camino hasta no poder continuar y luego retrocede.
function dfs<T>(graph: Graph<T>, start: T): T[] {
if (!graph.hasVertex(start)) return [];
const visited = new Set<T>();
const stack: T[] = [start];
const order: T[] = [];
while (stack.length > 0) {
const vertex = stack.pop()!;
if (visited.has(vertex)) continue;
visited.add(vertex);
order.push(vertex);
const neighbors = [...graph.neighbors(vertex)];
for (let i = neighbors.length - 1; i >= 0; i -= 1) {
if (!visited.has(neighbors[i])) {
stack.push(neighbors[i]);
}
}
}
return order;
}El orden exacto depende del orden de los vecinos y de cuándo se marcan. No existe un único orden DFS válido.
En BFS conviene marcar al encolar. Así cada vértice entra una sola vez.
Si marcas al extraer, varios vecinos pueden encolar el mismo vértice antes de que sea procesado, aumentando memoria y trabajo.
En DFS iterativo ambas estrategias son posibles, pero cambian el orden y la cantidad de duplicados en el stack. Declara la política y analiza esa implementación concreta.
Un traversal desde start solo visita su componente alcanzable. Para recorrer todo el grafo:
function traverseAll<T>(graph: Graph<T>): T[][] {
const visited = new Set<T>();
const components: T[][] = [];
for (const start of graph.vertices()) {
if (visited.has(start)) continue;
const component: T[] = [];
const stack = [start];
visited.add(start);
while (stack.length > 0) {
const vertex = stack.pop()!;
component.push(vertex);
for (const neighbor of graph.neighbors(vertex)) {
if (visited.has(neighbor)) continue;
visited.add(neighbor);
stack.push(neighbor);
}
}
components.push(component);
}
return components;
}Con adjacency list:
O(V + E);O(V) para visited, cola o stack.En un grafo no dirigido, cada arista aparece dos veces en la lista. El costo real es O(V + 2E), que se simplifica a O(V + E).
Con adjacency matrix, revisar vecinos exige recorrer una fila completa por vértice: O(V²).
En DFS recursivo, el call stack también cuenta y puede llegar a O(V) en un camino largo.
| Necesidad | Elección habitual |
|---|---|
| Menor cantidad de aristas | BFS |
| Niveles o cercanía | BFS |
| Explorar un camino completo | DFS |
| Información postorder | DFS |
| Memoria en un grafo muy ancho | Puede favorecer DFS |
| Memoria en un grafo muy profundo | Puede favorecer BFS |
Ninguno es universalmente más rápido: ambos inspeccionan V + E con adjacency list. Cambian el orden, el estado máximo y las propiedades que hacen visibles.
O(V + E) mientras se usa adjacency matrix.shift() y asumir cola O(1).visited en presencia de ciclos.Un sistema de dependencias puede modelarse como directed graph. Un servicio apunta a los servicios que necesita. DFS ayuda a detectar ciclos; topological sort produce un orden de construcción; connected components revelan grupos aislados.
El modelo debe responder qué significa la dirección. “A depende de B” puede almacenarse como A → B o B → A; ambos son posibles, pero cambian indegrees y orden topológico.
O(1) y grafos densos.visited evita ciclos y trabajo repetido.¿Por qué BFS no garantiza un shortest path cuando las aristas tienen pesos diferentes?
Porque BFS minimiza la cantidad de aristas, no la suma de sus pesos. Una ruta con dos aristas ligeras puede costar menos que una ruta directa con una arista pesada.