Graph Algorithms: BFS, DFS, Dijkstra, A*, Topological Sort

This chapter implements the fundamental graph algorithms: BFS, DFS, Dijkstra, A*, and topological sort.

Why This Matters

Graphs model networks, dependencies, maps, and state spaces. These algorithms are the building blocks of routing, scheduling, pathfinding, and compiler analysis.

Prerequisites

• c.ds.9 — graph representations.
• c.ds.4 — queues.
• c.ds.8 — priority queues.

Core Concept

• BFS: explore level by level using a queue. Finds shortest path in

unweighted graphs.

• DFS: explore as deep as possible, then backtrack. Used for connectivity,

cycles, topological sort.

• Dijkstra: shortest path in non-negative weighted graphs using a priority

queue.

• **A*:** Dijkstra + heuristic; explores toward the goal.
• Topological sort: order vertices so all edges go forward (DAG only).

Examples

BFS (unweighted shortest path)

void bfs(Graph *g, int start, int *dist)
{
    for (int i = 0; i < g->V; i++) dist[i] = -1;
    int q[MAXV]; int head = 0, tail = 0;
    q[tail++] = start; dist[start] = 0;
    while (head < tail) {
        int u = q[head++];
        for (Edge *e = g->adj[u]; e; e = e->next) {
            if (dist[e->to] == -1) {
                dist[e->to] = dist[u] + 1;
                q[tail++] = e->to;
            }
        }
    }
}

DFS

void dfs(Graph *g, int u, int *visited)
{
    visited[u] = 1;
    for (Edge *e = g->adj[u]; e; e = e->next)
        if (!visited[e->to])
            dfs(g, e->to, visited);
}

Dijkstra

/* dist[] initialized to INF; dist[src]=0 */
/* repeatedly extract min-dist unvisited vertex, relax edges */

Uses a priority queue for O((V+E) log V).

Topological sort (DFS-based)

void topo_dfs(Graph *g, int u, int *visited, int *order, int *idx)
{
    visited[u] = 1;
    for (Edge *e = g->adj[u]; e; e = e->next)
        if (!visited[e->to])
            topo_dfs(g, e->to, visited, order, idx);
    order[--*idx] = u;
}

How It Works

BFS uses FIFO order to guarantee shortest unweighted paths. DFS uses recursion/ stack to go deep first. Dijkstra greedily fixes the shortest distance to the closest unfinished vertex. A* adds a heuristic to guide the search. Topological sort uses DFS finishing order (or Kahn's algorithm with indegrees).

Variations

Kahn's algorithm (topological sort)

Repeatedly remove vertices with indegree 0, using a queue. Detects cycles if not all vertices are output.

Bidirectional search

Run BFS from both ends for faster unweighted shortest path.

Common Mistakes

• Forgetting to mark visited (infinite loop/cycles).
• Using Dijkstra with negative edges (use Bellman-Ford).
• An inadmissible A* heuristic (may miss optimal path).
• Assuming topological sort works on cyclic graphs.

Undefined Behavior

• Out-of-bounds array access (e.g., queue overflow). VERIFIED
• Dereferencing a NULL edge pointer.

Portability

• Plain C; the algorithms are portable. The priority-queue and queue are

implemented in earlier chapters.

Under the Hood

BFS/DFS are O(V+E). Dijkstra is O((V+E) log V) with a binary heap. A*'s performance depends on the heuristic. Topological sort is O(V+E).

Practical Usage

• Use BFS for unweighted shortest path and level-order traversal.
• Use DFS for connectivity, cycle detection, and topological sort.
• Use Dijkstra/A* for pathfinding and routing.
• Use topological sort for build dependency ordering.

Exercises

1. Implement BFS and DFS on an adjacency-list graph. 2. Implement Dijkstra with a priority queue. 3. Implement A* on a grid with a Manhattan heuristic. 4. Implement topological sort with both DFS and Kahn's algorithm.

Deep Challenge

Implement A* on a weighted grid, and compare it to Dijkstra. Explain how an admissible heuristic guarantees optimality and how an inconsistent heuristic affects correctness/performance.

Related Concepts

• c.ds.9 — graphs.
• c.ds.8 — priority queues.
• c.ds.4 — queues.

References

• CLRS, Sedgewick.

Verification

• Algorithm complexity and correctness are standard CS. VERIFIED
• No example was executed during generation unless noted. `Execution not

verified.`

Progress

• [ ] Read
• [ ] Understand
• [ ] Complete examples
• [ ] Complete exercises
• [ ] Complete deep challenge

Concept checkboxes

• [ ] BFS
• [ ] DFS
• [ ] Dijkstra
• [ ] A*
• [ ] Topological sort

Mastery levels