Data Structure & Algorithms
Algoritmos de grafos para componentes conectadas, detección de ciclos, topological sort, bipartición y strongly connected components.
Después de aprender BFS y DFS, muchas preguntas de grafos se reducen a mantener estado adicional durante el recorrido: componente, padre, color, grado de entrada o estado de visita.
El mismo traversal cambia de significado según el invariante que conservas.
Una componente conectada de un grafo no dirigido es un conjunto de vértices donde cada pareja está unida por algún camino.
Para contarlas:
function countComponents(graph: number[][]): number {
const visited = Array(graph.length).fill(false);
let components = 0;
for (let start = 0; start < graph.length; start += 1) {
if (visited[start]) continue;
components += 1;
const stack = [start];
visited[start] = true;
while (stack.length > 0) {
const node = stack.pop()!;
for (const neighbor of graph[node]) {
if (visited[neighbor]) continue;
visited[neighbor] = true;
stack.push(neighbor);
}
}
}
return components;
}Tiempo: O(V + E) con adjacency list. En un grafo no dirigido cada arista aparece normalmente dos veces, pero el factor dos no cambia Big O.
Al recorrer desde node, encontrar un vecino ya visitado no siempre indica ciclo: puede ser el padre desde el que llegaste.
function hasUndirectedCycle(graph: number[][]): boolean {
const visited = Array(graph.length).fill(false);
for (let start = 0; start < graph.length; start += 1) {
if (visited[start]) continue;
const stack: Array<[node: number, parent: number]> = [[start, -1]];
visited[start] = true;
while (stack.length > 0) {
const [node, parent] = stack.pop()!;
for (const neighbor of graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push([neighbor, node]);
} else if (neighbor !== parent) {
return true;
}
}
}
}
return false;
}Con aristas paralelas, la política de representación importa: dos aristas entre la misma pareja pueden formar un ciclo de longitud dos en un multigrafo.
En un directed graph, volver a cualquier nodo visitado no basta. Debes distinguir:
unvisited;visiting: está en el camino DFS actual;visited: su exploración terminó.Una arista hacia un nodo visiting es un back edge y demuestra un ciclo.
function hasDirectedCycle(graph: number[][]): boolean {
const state = Array(graph.length).fill(0); // 0, 1, 2
function visit(node: number): boolean {
if (state[node] === 1) return true;
if (state[node] === 2) return false;
state[node] = 1;
for (const neighbor of graph[node]) {
if (visit(neighbor)) return true;
}
state[node] = 2;
return false;
}
return graph.some((_, node) => state[node] === 0 && visit(node));
}La memoria incluye hasta O(V) de call stack. Para grafos muy profundos, una versión iterativa evita overflow del stack del runtime.
Un orden topológico coloca cada vértice antes que todos sus dependientes. Solo existe para un DAG.
Ejemplo:
compilar tipos → compilar aplicación → ejecutar tests → desplegarPuede haber varios órdenes válidos.
Usa el indegree, cantidad de aristas entrantes.
0;0.function topologicalSort(graph: number[][]): number[] | null {
const indegree = Array(graph.length).fill(0);
for (const neighbors of graph) {
for (const neighbor of neighbors) {
indegree[neighbor] += 1;
}
}
const queue: number[] = [];
for (let node = 0; node < graph.length; node += 1) {
if (indegree[node] === 0) queue.push(node);
}
const order: number[] = [];
let head = 0;
while (head < queue.length) {
const node = queue[head];
head += 1;
order.push(node);
for (const neighbor of graph[node]) {
indegree[neighbor] -= 1;
if (indegree[neighbor] === 0) queue.push(neighbor);
}
}
return order.length === graph.length ? order : null;
}Si quedan vértices sin procesar, pertenecen a un ciclo o dependen de él.
Tiempo: O(V + E). Memoria adicional: O(V).
Otra opción añade cada nodo al resultado después de visitar todos sus vecinos y luego revierte la lista. Debe combinarse con los tres estados para detectar ciclos.
Kahn es cómodo cuando necesitas indegrees, procesamiento por capas o detectar qué tareas están disponibles. DFS refleja naturalmente dependencias recursivas.
Un grafo es bipartito si puede dividirse en dos grupos y cada arista conecta grupos diferentes.
Equivale a poder colorearlo con dos colores. Un grafo no dirigido es bipartito si y solo si no contiene ciclos impares.
function isBipartite(graph: number[][]): boolean {
const color = Array(graph.length).fill(-1);
for (let start = 0; start < graph.length; start += 1) {
if (color[start] !== -1) continue;
color[start] = 0;
const queue = [start];
let head = 0;
while (head < queue.length) {
const node = queue[head];
head += 1;
for (const neighbor of graph[node]) {
if (color[neighbor] === -1) {
color[neighbor] = 1 - color[node];
queue.push(neighbor);
} else if (color[neighbor] === color[node]) {
return false;
}
}
}
}
return true;
}Aplicaciones: asignar dos tipos incompatibles, matching bipartito, horarios y partición de relaciones.
En un directed graph, una SCC contiene vértices que se alcanzan mutuamente. Algoritmos como Kosaraju y Tarjan las encuentran en O(V + E).
Conceptualmente permiten comprimir cada SCC en un solo nodo. El grafo condensado resultante siempre es un DAG.
Es contenido avanzado, pero conecta ciclos dirigidos con topological sorting.
Con adjacency matrix, explorar vecinos de un nodo cuesta O(V), aunque tenga pocos. Un recorrido completo puede costar O(V²).
Con adjacency list, el recorrido cuesta O(V + E). La complejidad no pertenece solo al algoritmo: depende de cómo representas el grafo.
BFS y DFS son motores de exploración. El problema se resuelve con el estado que añades: parent para ciclos no dirigidos, tres colores para ciclos dirigidos, indegree para topological sort y dos colores para bipartición.
¿Por qué un grafo dirigido puede tener una arista hacia un nodo ya procesado sin que exista un ciclo?
Porque el nodo puede pertenecer a otra rama cuya exploración ya terminó. Solo una arista hacia un nodo que sigue en el camino DFS actual, estado visiting, regresa a un ancestro y demuestra un ciclo.