Graph Algorithms — BFS/DFS Applications, Topological Sort, Shortest Paths

Apply graph traversals to reachability, dependencies, and shortest paths.

Est. 120 min Updated Suggest a fix
💡 Note
Prerequisites: the Graphs lesson (Lesson 16), queues, stacks/recursion, and Big O. The examples use a small adjacency matrix so every storage detail is visible; for sparse large graphs, adjacency lists reduce traversal to O(V + E).

Objectives and graph vocabulary

After this lesson you should be able to select BFS or DFS for a graph task, use topological order only for a directed acyclic graph (DAG), and select a shortest-path algorithm from the edge-weight constraints. A vertex is a node, an edge is a connection, V is the number of vertices, and E is the number of edges. Always clarify whether edges are directed and whether weights can be negative.

🎯 Pro Tip
This is a concept-and-implementation lesson, not another interview question collection. For problem recognition, dry runs, and placement practice, use Interview Problem-Solving Patterns →.

1. BFS: layers, reachability, and unweighted distance

Breadth-first search visits vertices in increasing number of edges from a source. A FIFO queue preserves this layer order. Mark a vertex visited when you enqueue it, not when you remove it: otherwise several neighbours can enqueue the same vertex before its first visit. BFS finds a shortest path measured in edge count when every edge has equal cost.

BFS distances with an adjacency matrix · C
#include <stdbool.h>
#define MAX_V 100

void bfs_distances(int n, int graph[MAX_V][MAX_V], int source, int distance[MAX_V]) {
    int queue[MAX_V];
    int front = 0, back = 0;
    for (int v = 0; v < n; v++) distance[v] = -1;
    distance[source] = 0;
    queue[back++] = source;
    while (front < back) {
        int current = queue[front++];
        for (int next = 0; next < n; next++) {
            if (graph[current][next] && distance[next] == -1) {
                distance[next] = distance[current] + 1;
                queue[back++] = next;
            }
        }
    }
}

This fixed-array example assumes 0 < n ≤ MAX_V and a valid source index. A distance of -1 means unreachable. To reconstruct a shortest route, store parent[next] = current at the same moment that you first set the distance; then walk parents backward from the destination and reverse the route. With a matrix, scanning all possible neighbours costs O(V²); with adjacency lists it is O(V + E). Queue capacity V is sufficient because each vertex is enqueued at most once.

2. DFS: components, cycle reasoning, and exploration

Depth-first search follows a branch until it cannot continue, then backtracks. Recursion implicitly uses the call stack; an explicit stack avoids recursion-depth limits on a very deep graph. For an undirected graph, start DFS from every unvisited vertex to count connected components. For directed cycle detection, use three states—unvisited, active on the current recursion path, and complete—because a visited edge alone does not prove a cycle.

Recursive DFS over a matrix · C
#define MAX_V 100

void dfs_visit(int n, int graph[MAX_V][MAX_V], int vertex, int visited[MAX_V]) {
    visited[vertex] = 1;
    for (int next = 0; next < n; next++) {
        if (graph[vertex][next] && !visited[next]) {
            dfs_visit(n, graph, next, visited);
        }
    }
}

int count_components(int n, int graph[MAX_V][MAX_V]) {
    int visited[MAX_V] = {0};
    int components = 0;
    for (int v = 0; v < n; v++) {
        if (!visited[v]) {
            components++;
            dfs_visit(n, graph, v, visited);
        }
    }
    return components;
}
⚠️ Important
This component routine assumes an undirected graph. For directed graphs, “connected component” may mean weakly connected or strongly connected; those are different definitions and need different algorithms.

3. Topological sorting: order prerequisites

A topological order places every prerequisite before the task that depends on it. It exists exactly when a directed graph has no cycle. Kahn’s algorithm repeatedly removes a zero-indegree vertex (one with no remaining prerequisites), then decreases the indegree of its outgoing neighbours. If fewer than V vertices are emitted, a cycle remains. With adjacency lists this is O(V + E); the matrix version below scans rows and costs O(V²).

Kahn's algorithm (matrix representation) · C
#include <stdbool.h>
#define MAX_V 100

bool topological_order(int n, int graph[MAX_V][MAX_V], int order[MAX_V]) {
    int indegree[MAX_V] = {0};
    int queue[MAX_V], front = 0, back = 0, count = 0;
    for (int from = 0; from < n; from++)
        for (int to = 0; to < n; to++)
            if (graph[from][to]) indegree[to]++;
    for (int v = 0; v < n; v++)
        if (indegree[v] == 0) queue[back++] = v;
    while (front < back) {
        int current = queue[front++];
        order[count++] = current;
        for (int next = 0; next < n; next++) {
            if (graph[current][next] && --indegree[next] == 0)
                queue[back++] = next;
        }
    }
    return count == n;
}

There can be multiple valid orders; do not compare one arbitrary output against a single expected sequence. Validate every directed edge u → v by checking that u occurs earlier than v. A failed result is useful: report a dependency cycle rather than returning a partial order as if it were complete.

4. Shortest paths: use the edge model

Graph conditionAlgorithmCore ideaTypical complexity
Unweighted / equal-cost edgesBFSFirst discovery is minimum edge countO(V + E) with adjacency lists
Non-negative weightsDijkstra'sRepeatedly finalise the closest unsettled vertexO((V + E) log V) with a binary heap
Negative weights; no reachable negative cycleBellman–FordRelax every edge up to V − 1 roundsO(VE)
All pairs, small/dense graphFloyd–WarshallAllow each vertex as an intermediateO(V³) time, O(V²) space

Dijkstra is not valid for negative edge weights: a vertex thought to be finished can later receive a shorter path. Bellman–Ford can also detect a negative cycle reachable from the source if another relaxation succeeds after V−1 rounds. Shortest paths are undefined as a finite minimum when such a reachable negative cycle can be traversed repeatedly.

Dijkstra for non-negative weights (matrix, O(V²)) · C
#include <stdbool.h>
#include <limits.h>
#define MAX_V 100
#define INF (LLONG_MAX / 4)

bool dijkstra(int n, long long weight[MAX_V][MAX_V], int source,
              long long distance[MAX_V]) {
    if (n <= 0 || n > MAX_V || source < 0 || source >= n) return false;
    for (int from = 0; from < n; from++)
        for (int to = 0; to < n; to++)
            if (weight[from][to] != INF && (weight[from][to] < 0 || weight[from][to] >= INF)) return false;
    int done[MAX_V] = {0};
    for (int v = 0; v < n; v++) distance[v] = INF;
    distance[source] = 0;
    for (int step = 0; step < n; step++) {
        int current = -1;
        for (int v = 0; v < n; v++)
            if (!done[v] && (current == -1 || distance[v] < distance[current]))
                current = v;
        if (current == -1 || distance[current] == INF) break;
        done[current] = 1;
        for (int next = 0; next < n; next++) {
            if (weight[current][next] == INF) continue;
            long long candidate = distance[current] + weight[current][next];
            if (candidate < distance[next]) distance[next] = candidate;
        }
    }
    return true;
}

Initialize every absent edge to INF and the diagonal to zero. This version validates the non-negative-weight precondition and reserves the INF range for missing edges so additions stay representable. A binary heap reduces the search cost on sparse graphs; when using a heap with duplicate entries, discard stale entries whose key no longer equals the best known distance.

5. Recover a route and verify your result

Distances answer “how far?” but many applications need the route. In BFS or Dijkstra, set a predecessor only when a strict improvement (or first discovery for BFS) is accepted. Starting at the destination, follow parents until reaching the source; if the destination has infinite distance or no parent chain to the source, it is unreachable. Test source equal to destination, isolated vertices, parallel edges, and ties. Ties can produce different but equally valid paths.

6. Common mistakes

  • Marking visited on dequeue: duplicate queue entries can fill memory and repeat work. Mark when enqueuing.
  • Using DFS for shortest unweighted distance: DFS discovers a path, not necessarily a shortest one. Use BFS for equal-cost edges.
  • Topologically sorting a cyclic graph: a partial list is not a valid complete schedule. Check that the output count is V.
  • Using Dijkstra with negative edges: its greedy finalisation proof fails. Choose Bellman–Ford when negative weights are allowed.

7. Practice

  1. Return BFS distances and parent pointers from a source in a disconnected undirected graph.
  2. Count connected components. Explain why the routine must start a traversal from every still-unvisited vertex.
  3. Build a course schedule order with Kahn’s algorithm and detect a cycle. Verify edge ordering instead of expecting one exact order.
  4. Implement Bellman–Ford and return whether a source-reachable negative cycle exists.
  5. Compare matrix and list memory use for a graph with many vertices but few roads; justify the representation and complexity.

🎯 Key Takeaways

  • ✓BFS explores by edge-count layers and gives shortest paths in unweighted graphs.
  • ✓DFS supports exhaustive exploration and component/cycle reasoning, but not shortest-path guarantees.
  • ✓Topological sorting is defined only for DAGs; emitted count detects a cycle.
  • ✓Choose shortest-path algorithms from weight constraints: BFS, Dijkstra, Bellman–Ford, or Floyd–Warshall.
  • ✓State graph direction, weight, and connectivity assumptions before implementing.
  • ✓Use the Interview Problem-Solving Patterns unit for separate pattern drills and dry runs.

Next

Apply state-and-transition reasoning to classic dynamic programming shapes.

Lesson 24 · Dynamic Programming Patterns →

HELP US IMPROVE

How was this lesson?

Your note is shared with the Chaduvuko team for review. Please don’t include personal or sensitive information.

Choose your feedback

Spotted a mistake or something unclear? Suggest a fix on GitHub or email us. Select the text first and it is quoted for you.

Share

Discussion

0

Have a better approach? Found something outdated? Share it — your knowledge helps everyone learning here.

Continue with GitHub
Loading...