Graphs: traversals, Dijkstra and A*

A graph is a set of nodes (V) connected by edges (E). Traversals visit every node; Dijkstra and A* find shortest paths when edges have weights.

Representing a graph

• Adjacency list: for each node, the list of its neighbors. O(|V| + |E|) memory; ideal for sparse graphs.
• Adjacency matrix: a |V| × |V| table. "Are u and v neighbors?" in O(1), but O(|V|²) memory.

In the examples, when a node has several neighbors, they are taken in alphabetical order. The result depends on this convention: check the one your course uses.

Depth-first search (DFS)

Go as deep as possible before backtracking. It uses a stack, or recursion.

dfs(u):
    mark u as visited
    for each neighbor v of u (in order):
        if v is not visited: dfs(v)

Example graph (undirected): A–B, A–C, B–D, C–D, C–F, D–E.

DFS from A: A → B → D (first unvisited neighbor of B) → C (first unvisited neighbor of D) → F. C has no free neighbor left: back to D, which still has E. Visit order: A, B, D, C, F, E.

Breadth-first search (BFS)

Nodes are visited in "layers": first the start, then all its neighbors, then the neighbors' neighbors. It uses a queue (first in, first out).

bfs(start):
    queue = [start]; mark start as discovered
    while the queue is not empty:
        u = dequeue()
        visit u
        for each neighbor v of u (in order):
            if v is not discovered: mark it and enqueue it

BFS from A on the same graph: queue [A] → visit A, enqueue B, C → visit B, enqueue D → visit C, enqueue F (D is already discovered) → visit D, enqueue E → F → E. Order: A, B, C, D, F, E.

In an unweighted graph, BFS finds the path with the fewest edges. Both traversals cost O(|V| + |E|).

Dijkstra: shortest paths

With non-negative weights, Dijkstra computes the shortest distance from the start to every other node.

1. d(start) = 0, every other distance = ∞.
2. Choose the unvisited node with the smallest distance. Its distance becomes final.
3. Relax each of its neighbors v: if d(u) + w(u, v) < d(v), then d(v) = d(u) + w(u, v).
4. Repeat until every reachable node has been visited.

Example: edges A–B (4), A–C (1), B–C (2), B–D (5), C–D (8), D–E (3), start A.

The direct edge A–B (4) is not the best route: going through C costs 3. With a binary heap as the priority queue, Dijkstra costs O((|E| + |V|) log |V|).

A*: searching toward the goal

When looking for a path to a single goal, A* adds an estimate of the remaining distance. Every node in the open list has a priority:

f(n) = g(n) + h(n)

• g(n): the cost of the best known path from the start to n (Dijkstra's d(n));
• h(n): an estimate of the cost from n to the goal (straight-line distance, for example).

Always choose the open node with the smallest f, and stop when the goal is chosen (not when it is discovered).

Example: same graph, from A to E, with h(A) = 7, h(B) = 5, h(C) = 6, h(D) = 3, h(E) = 0.

1. Open: A (f = 0 + 7 = 7). Choose A → B (g 4, f 9) and C (g 1, f 7).
2. Choose C (f 7) → B improves (g 3, f 8), D (g 9, f 12).
3. Choose B (f 8) → D improves (g 8, f 11).
4. Choose D (f 11) → E (g 11, f 11).
5. Choose E: it is the goal, cost 11.

A good heuristic

• Admissible: h never overestimates the true remaining cost. A* then finds the optimal path.
• Consistent: h(u) ≤ w(u, v) + h(v) for every edge. A closed node then never needs to be reopened.

With h = 0 everywhere, A* becomes exactly Dijkstra. The closer h is to the true cost, the fewer nodes A* explores.

Two definitions to know

• Eulerian path: uses every edge exactly once. It exists if the graph is connected and has 0 or 2 nodes of odd degree.
• Hamiltonian path: visits every node exactly once. Deciding whether one exists is NP-complete.