Graph Algorithms Explained — BFS, DFS, Topological Sort & SCCs | Chapter 20 in Introduction to Algorithms

Graph algorithms are at the heart of many critical operations in computer science, from web crawling and pathfinding to task scheduling and dependency resolution. Chapter 20 of Introduction to Algorithms (CLRS) provides a comprehensive overview of graph representations, traversal algorithms like BFS and DFS, and advanced applications such as topological sorting and strongly connected components (SCCs). Whether you're studying for AP Computer Science or brushing up on algorithm fundamentals, this chapter is essential reading.

📺 Watch the full video above for a visual breakdown of each algorithm and its application, or keep reading for an in-depth written explanation.

Graph Representations

Graphs can be represented in two main ways: adjacency lists and adjacency matrices. Each has trade-offs in space and time complexity depending on the graph’s density.

• Adjacency List: Best for sparse graphs. Space complexity is Θ(V + E). Stores all neighbors for each vertex.
• Adjacency Matrix: Best for dense graphs. Space complexity is Θ(V²). Allows O(1) edge checks.
• Weighted graphs store edge weights directly in the matrix or alongside the adjacency list.
• Additional attributes (like color, distance, predecessor) are often stored in parallel arrays or object fields.

Breadth-First Search (BFS)

BFS explores a graph layer by layer, beginning at a source vertex and radiating outward. It’s useful for finding the shortest path (in edge count) in unweighted graphs.

• Uses a queue to track nodes to explore.
• Color coding: white (undiscovered), gray (discovered), black (fully explored).
• Each node stores:
  • v.d = distance from source
  • v.pi = predecessor
• Running time: O(V + E) using an adjacency list.
• Results in a breadth-first tree reflecting shortest paths.

Depth-First Search (DFS)

DFS dives deep into the graph recursively before backtracking. It’s ideal for exploring all nodes and understanding graph structure.

• Uses recursion (or an explicit stack).
• Color coding and timestamps:
  • v.d = discovery time
  • v.f = finish time
• Creates a DFS forest if the graph is disconnected.
• Running time: Θ(V + E).
• Edge classification in directed graphs:
  • Tree edge
  • Back edge (indicates cycle)
  • Forward edge
  • Cross edge

Topological Sort

This algorithm orders vertices of a directed acyclic graph (DAG) such that for every edge (u, v), vertex u comes before v.

• Performed using DFS: vertices are added to a list as they finish, then the list is reversed.
• If DFS finds any back edge, the graph is not a DAG.
• Time complexity: Θ(V + E).

Strongly Connected Components (SCCs)

An SCC is a maximal group of vertices where every vertex is reachable from every other. SCCs reveal deep structural properties in directed graphs.

The algorithm to find SCCs:

1. Run DFS on G to compute finish times.
2. Compute the transpose graph Gᵀ (edges reversed).
3. Run DFS on Gᵀ in decreasing order of original finish times.
4. Each resulting DFS tree is one SCC.

This method runs in Θ(V + E) time and relies on the acyclic nature of the component graph.

Glossary of Key Terms

• Adjacency List: List of neighbors per vertex.
• Adjacency Matrix: VxV matrix showing edges.
• Breadth-First Tree: Tree formed by BFS reflecting shortest paths.
• DFS Forest: Group of DFS trees from disconnected components.
• Topological Sort: Linear vertex order in a DAG.
• Strongly Connected Component: Maximal set of mutually reachable vertices.
• Transpose Graph: Graph with all edges reversed.
• DFS Edge Types: Tree, back, forward, cross.

Conclusion

Chapter 20 offers a powerful toolkit for understanding and manipulating graphs. BFS and DFS provide foundational strategies for exploring connectivity and structure, while topological sort and SCC algorithms tackle advanced organizational and dependency-related challenges. These graph algorithms underpin many real-world systems, from compilers and schedulers to navigation apps and recommendation engines.

📽️ For a full walkthrough with diagrams and examples, watch the YouTube summary here.

📘 Explore more chapters from Introduction to Algorithms by subscribing to the Last Minute Lecture channel.

If you found this breakdown helpful, be sure to subscribe to Last Minute Lecture for more chapter-by-chapter textbook summaries and academic study guides.