Overview
Once a problem is expressed as a graph, a small set of algorithms
Traversal: BFS & DFS
Breadth-first and depth-first search both visit every vertex reachable from a start point, in
Shortest Paths
"Shortest" means fewest edges on an unweighted graph and lowest total weight on a weighted one, and
Topological Sort
A topological sort orders the vertices of a directed acyclic graph so every edge points forward —
Cycle Detection
A cycle is a path that leaves a vertex and, by following edges, returns to it. That definition reads
Minimum Spanning Trees
Given a connected, undirected, weighted graph, a spanning tree picks exactly V - 1 edges that keep
Strongly Connected Components
In a directed graph, two vertices are strongly connected if each can reach the other — a path
Bipartite Graphs & Coloring
A graph is bipartite when its vertices split into two groups such that every edge runs between
Network Flow
A flow network is a directed graph where every edge has a capacity, one vertex is a source pumping
A* & Heuristic Search
Dijkstra's algorithm finds the shortest path to every vertex by always expanding the closest
Cheat Sheet
This page is a reference, not a tutorial — see Graph Algorithms Overview for a first