After reading this
- Model nodes and edges
- Tell BFS from DFS
- Recognize path problems
Nodes and edges
A graph can be directed or undirected, weighted or unweighted. Edge shape determines the question you can answer.
js
const network = {
A: ['B', 'C'],
B: ['D'],
C: ['D'],
D: []
};BFS: layer by layer
Breadth-first search uses a queue. It explores close neighbors first and finds the path with the fewest edges in an unweighted graph.
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: deep first
Depth-first search uses recursion or a stack. It fits dependency, cycle, and full-branch exploration problems.
Graph traversal● interactive
A1B2C3D4E5
Traverse a network
Find the minimum number of connections between two people in an unweighted network.
Show a hint
BFS preserves distance by layers.