Introduction

Why Graph Algorithms?

Graphs are one of the most powerful abstractions in computer science. They model relationships between things — web pages and links, cities and roads, users and friendships, tasks and dependencies. Nearly every complex problem at scale can be framed as a graph problem.

  • Social networks — Facebook, LinkedIn, Twitter are graphs. Shortest path gives degrees of separation. PageRank ranks influence.
  • Maps & Navigation — Google Maps uses Dijkstra and A* to find shortest routes.
  • Compilers — Topological sort orders declarations. Cycle detection finds circular imports.
  • Networking — Routing protocols (OSPF) use shortest-path algorithms.
  • Machine Learning — Knowledge graphs, graph neural networks, dependency parsing.

What You Will Learn

This course implements the core graph algorithms from scratch in Python:

  • Representations: adjacency lists — the foundation of all graph algorithms
  • Traversals: BFS (level-by-level) and DFS (deep-first) — the building blocks
  • Connectivity: has_path, connected components, bipartite check
  • Cycle detection: undirected (parent tracking) and directed (3-color DFS)
  • Topological sort: Kahn's algorithm for ordering DAGs
  • Shortest paths: Dijkstra (non-negative weights) and Bellman-Ford (negative weights)
  • Union-Find: path compression and union by rank — nearly O(1) per operation
  • Minimum Spanning Tree: Kruskal's algorithm using Union-Find
  • PageRank: the algorithm behind Google Search

Every function is tested against concrete examples with known correct outputs.

Next →