What are Graph Algorithms?
A graph is a collection of nodes connected by edges. Unlike a tree, a graph can have cycles, several routes to one node, and disconnected parts.
You need to know queues, stacks, maps, and basic traversal. The short version is: choose the traversal whose processing order matches the question the graph is asking.
The Core Idea: Process Relationships
In LC 207: Course Schedule, an edge means one course must be completed before another. Course 0 has no prerequisite, so it can be processed first.
What becomes possible after course 0 is finished? We remove its outgoing dependency edges. Any course whose remaining prerequisite count reaches zero joins the queue.
It is like planning jobs on a construction site. A crew can begin a job only after every job it depends on has been crossed off.
How Kahn's Topological Sort Works
The Rule You Keep True
For topological sort, the in-degree of an unprocessed node equals the number of its prerequisites that are still unprocessed. Only nodes with zero remaining prerequisites may enter the ready queue.
Different graph questions need different processing orders:
- BFS or DFS answers reachability and connected-component questions.
- Topological sort orders directed dependencies and detects dependency cycles.
- Dijkstra expands the node with the smallest known distance for non-negative weighted edges.
- Union-Find tracks components while edges are added.
LC 207: Cycle Detection is the one that usually trips us up. The queue can become empty before every node is processed. That is not an ordinary finish; it means the remaining nodes depend on one another in a cycle.
Picking the Right Shape
From Rule to Code
- Decide what each node and directed edge means.
- Build an adjacency list and any counts or distances required by the algorithm.
- Initialize the queue, stack, or priority queue with valid starting nodes.
- Process one node, then update or discover its neighbors.
- Compare the processed result with the expected node count or requested target.
Each node and edge is processed a bounded number of times. Traversal and topological sort take O(V + E) time, while heap-based Dijkstra takes O((V + E) log V).
When to use it
- •The input describes objects connected by relationships or moves.
- •You need reachability, ordering, components, cycles, or shortest paths.
- •A dependency must be completed before another item can begin.
- •Several routes may lead to the same node.
How to identify it
- •The prompt mentions nodes, edges, courses, roads, accounts, dependencies, or connections.
- •The input is an edge list, adjacency list, matrix, or grid of possible moves.
- •There is no single parent for each item, unlike a tree.
- •The answer depends on walking relationships rather than array position.
Key insights
- →An adjacency list records the neighbors that can be reached from each node.
- →Visited state prevents repeated work and infinite loops.
- →Topological order exists only for a directed graph without a cycle.
- →Kahn's algorithm removes nodes with zero remaining prerequisites.
- →Dijkstra finalizes the smallest known distance first when edge weights are non-negative.
Common mistakes
- 01Reversing the direction of prerequisite edges.
- 02Forgetting to include nodes that have no outgoing edges in the adjacency structure.
- 03Treating a disconnected graph as if traversal from one node reaches everything.
- 04Using ordinary BFS when edge weights differ.
- 05Using Dijkstra when a negative edge can make a finalized distance smaller later.