Graph Algorithms — BFS/DFS Applications, Topological Sort, Shortest Paths
Apply graph traversals to reachability, dependencies, and shortest paths.
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.
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.
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.
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²).
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 condition | Algorithm | Core idea | Typical complexity |
|---|---|---|---|
| Unweighted / equal-cost edges | BFS | First discovery is minimum edge count | O(V + E) with adjacency lists |
| Non-negative weights | Dijkstra's | Repeatedly finalise the closest unsettled vertex | O((V + E) log V) with a binary heap |
| Negative weights; no reachable negative cycle | Bellman–Ford | Relax every edge up to V − 1 rounds | O(VE) |
| All pairs, small/dense graph | Floyd–Warshall | Allow each vertex as an intermediate | O(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.
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
- Return BFS distances and parent pointers from a source in a disconnected undirected graph.
- Count connected components. Explain why the routine must start a traversal from every still-unvisited vertex.
- Build a course schedule order with Kahn’s algorithm and detect a cycle. Verify edge ordering instead of expecting one exact order.
- Implement Bellman–Ford and return whether a source-reachable negative cycle exists.
- 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.
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.
Spotted a mistake or something unclear? Suggest a fix on GitHub or email us. Select the text first and it is quoted for you.
Discussion
0Have a better approach? Found something outdated? Share it — your knowledge helps everyone learning here.
