Al terminar esta nota
- Modelar nodos y aristas
- Diferenciar BFS de DFS
- Reconocer problemas de caminos
Nodos y aristas
Un grafo puede ser dirigido o no dirigido, ponderado o sin peso. La forma de la arista define la pregunta que podés responder.
js
const red = {
A: ['B', 'C'],
B: ['D'],
C: ['D'],
D: []
};BFS: por capas
Breadth-first search usa una cola. Explora primero los vecinos cercanos y encuentra el camino con menos aristas en un grafo sin peso.
js
function bfs(graph, start) {
const queue = [start];
const visited = new Set([start]);
while (queue.length) {
const node = queue.shift();
for (const next of graph[node]) {
if (!visited.has(next)) {
visited.add(next); queue.push(next);
}
}
}
}DFS: en profundidad
Depth-first search usa recursión o un stack. Es útil para dependencias, ciclos y explorar una rama completa antes de volver.
Recorrido de grafos● interactivo
A1B2C3D4E5
Recorré una red
Encontrá la cantidad mínima de conexiones entre dos personas en una red sin pesos.
Mostrar una pista
BFS conserva la distancia por capas.