sdlc.dev

Data structures and algorithms path · Searching and reusing work · Topic 11 of 13

Graphs: BFS, DFS and shortest paths

Not started

A graph is a set of nodes connected by edges, which may have a direction and a cost. Most graph algorithms are the same loop with a different container: take a node out of the frontier, look at its neighbours, and put the new ones in. Use a queue and you get breadth-first search, which explores in rings of increasing distance. Use a stack and you get depth-first search. Use a priority queue ordered by distance and you get Dijkstra's shortest paths.

Why it matters: Dependency resolution, route planning, social networks, build systems, crawlers and permission checks are all graph searches in disguise.

  1. 1Adjacency lists

    Store each node's neighbours in a list or map. It takes space proportional to the edges and makes "visit every neighbour" cheap.

  2. 2BFS uses a queue

    Breadth-first search visits nodes in order of distance from the start, so it finds shortest paths when every edge costs the same.

  3. 3DFS uses a stack

    Depth-first search goes as deep as it can before backtracking. It is the basis of cycle detection and topological sorting.

  4. 4Weights need Dijkstra

    With non-negative edge costs, always expand the closest unsettled node, using a priority queue. Negative costs need Bellman-Ford.

1

Watch it run

Play it or step through. Every step says what just happened.

const graph = { A: ["B", "C"], B: ["D"], C: ["D", "E"], D: ["F"], E: ["F"], F: [] };function bfs(start) {  const dist = { [start]: 0 };  const queue = [start];  while (queue.length > 0) {    const node = queue.shift();    console.log(node, dist[node]);    for (const next of graph[node]) {      if (!(next in dist)) {        dist[next] = dist[node] + 1;        queue.push(next);      }    }  }}bfs("A");

Queue (frontier)

Discovered but not yet visited; oldest first

empty

Visiting

The node just taken from the queue

empty

Finished

Node = distance from A

empty

Console0 lines

    Step 0 of 13

    Nothing has run yet. The graph has edges A→B, A→C, B→D, C→D, C→E, D→F and E→F. dist doubles as the set of nodes already discovered.

    queue.shift() is fine for a small graph. For millions of nodes, keep a head index instead so dequeuing stays O(1); the whole search is then O(nodes + edges).

    2

    Try it yourself

    Change the code, predict the order, then run it for real in your browser.

    ⌘/Ctrl + Enter
    OutputNot run yet

    Press Run to see what your code prints, in order.

    Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

    3

    Check yourself

    3 questions. Get them all right to finish this topic.

    1. 1.Why does BFS find the shortest path in an unweighted graph?
    2. 2.In the trace, D is reachable from both B and C. Why is it only queued once?
    3. 3.Which algorithm fits "find the cheapest route when roads have different travel times, none negative"?

    0 of 3 right so far. Get all three to finish this topic.

    Storing a graph

    An adjacency list maps each node to its neighbours, like the graph object above. It uses space proportional to the number of edges and lets you loop over a node's neighbours directly, which is what searches do. An adjacency matrix, an n × n grid of booleans or weights, answers "is there an edge from u to v?" in O(1) but uses n² space, so it only suits small or dense graphs. Most real graphs (road networks, follower graphs, package dependencies) are sparse, so lists win.

    Depth-first search

    Swap the queue for a stack (or use recursion) and the search dives down one path before backtracking. DFS doesn't find shortest paths, but the order in which it finishes nodes is very useful. It detects cycles (meeting a node that is still on the current path), and reversing the finish order of a directed acyclic graph gives a topological order, an order in which every task comes after the tasks it depends on. Package managers, build tools and spreadsheet recalculation all need that; Python ships it as graphlib.TopologicalSorter.

    Weighted shortest paths

    When edges have costs, the node with the fewest hops isn't necessarily the cheapest. Dijkstra's algorithm keeps a tentative distance for every node and always expands the unsettled node with the smallest one, which a priority queue provides. With a binary heap it runs in O((V + E) log V). It requires non-negative weights; with negative edges use Bellman–Ford, and for one target on a map, A* adds an estimate of the remaining distance to search towards the goal first.

    ⌘/Ctrl + Enter
    OutputNot run yet

    Press Run to see what your code prints, in order.

    Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

    The direct-looking route home → station → office costs 16 and the park route costs 14; Dijkstra finds 13 through the café and the station. Sorting the frontier on every step keeps the example short; swap in the min-heap from the heaps topic to get the O((V + E) log V) bound.

    Go deeper