Algorithms
Graph Algorithms (Core)
Difficulty: Intermediate
Webpack figures out the order to compile your modules using topological sort. Google Maps figures out the route to your destination using Dijkstra. Your CI system rejects circular imports using cycle detection. The same handful of graph...
Graph Algorithms (Core)
Webpack figures out the order to compile your modules using topological sort. Google Maps figures out the route to your destination using Dijkstra. Your CI system rejects circular imports using cycle detection. The same handful of graph algorithms power an enormous slice of real infrastructure, and almost all of them are short additions to a BFS or DFS skeleton you already wrote.
Graph Algorithms (Core) covers that handful in detail. You will implement topological sort in two ways (Kahn's BFS-with-in-degree algorithm and the DFS-reverse-postorder algorithm), cycle detection on undirected graphs (DFS with parent tracking) and on directed graphs (DFS with white/gray/black coloring), Dijkstra's shortest-path algorithm with a min-heap and the relaxation invariant that makes it work, connected-component counting via DFS or Union-Find, and bipartite checking via two-color BFS. Along the way you will see why Dijkstra fails on negative edge weights, which motivates Bellman-Ford in the advanced lesson later.
In BFS & DFS (Intro), you wrote the two traversal skeletons. Weighted Graph Representation gave you the adjacency-list-of-tuples format that Dijkstra and friends actually consume. This lesson is where those primitives turn into named algorithms with clear use cases.
From here, Greedy (Intro) introduces a different paradigm: instead of exploring every option, commit to the locally best choice at each step.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Implement topological sort using both Kahn's BFS-based algorithm and DFS-based reverse post-order.
Detect cycles in directed graphs using DFS coloring and in undirected graphs using parent tracking.
Implement Dijkstra's shortest path algorithm using a priority queue and explain why it fails with negative weights.
Count connected components using DFS/BFS and explain how Union-Find provides an alternative approach.
Determine whether a graph is bipartite using BFS/DFS 2-coloring.
Analyze the time and space complexity of each core graph algorithm.
Why This Matters
01
Topological sort is the backbone of build systems (Make, Webpack), course prerequisite planning, and any pipeline where tasks have dependencies.
02
Dijkstra's algorithm powers GPS navigation, network routing protocols (OSPF), and is one of the most frequently tested graph algorithms in interviews.
03
Cycle detection prevents infinite loops in dependency graphs and is essential for validating DAGs in compilers and package managers.
04
Connected components and bipartite checking appear in social network analysis, matching problems, and are building blocks for more advanced graph algorithms.
Key Terms
7 terms you'll encounter in this lesson
Topological Sort
A linear ordering of vertices in a DAG such that for every directed edge (u, v), vertex u appears before v. Only defined for Directed Acyclic Graphs.
DAG
Directed Acyclic Graph — a directed graph with no cycles. DAGs model dependency relationships like task scheduling and course prerequisites.
In-degree
The number of incoming edges to a vertex. In Kahn's algorithm, vertices with in-degree 0 have no unresolved dependencies and can be processed first.
Relaxation
The process in Dijkstra's algorithm of updating the shortest known distance to a vertex when a shorter path is found through a neighbor.
Connected Component
A maximal subset of vertices such that every pair of vertices is connected by a path. In a directed graph, the analogous concept is a strongly connected component.
Bipartite Graph
A graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other. Equivalently, a graph that is 2-colorable.
Negative weight edge
An edge with a negative cost. Dijkstra's algorithm assumes non-negative weights; negative weights require Bellman-Ford.
Heads Up
Common misconceptions to watch out for
"Topological sort gives a unique ordering"
A DAG can have multiple valid topological orderings. Kahn's algorithm returns one based on processing order of in-degree-0 vertices; DFS gives another. The ordering is unique only if the DAG forms a single chain.
"Dijkstra's algorithm works with negative edge weights"
Dijkstra relies on the greedy property that once a vertex is finalized, no shorter path exists. Negative weights violate this because a later edge could reduce the total cost. Use Bellman-Ford for graphs with negative weights.
"Cycle detection in directed graphs only needs a visited set"
A simple visited set causes false positives in directed graphs. You need three states (white/gray/black or unvisited/in-progress/done): a cycle exists only when you encounter a gray (in-progress) node, meaning you have found a back edge in the current DFS path.
"BFS always finds the shortest path"
BFS finds the shortest path only in unweighted graphs (fewest edges). In weighted graphs, the path with fewest edges may have higher total weight. Dijkstra's algorithm accounts for edge weights to find the true shortest path.