Graph Algorithms Guide

Graph Theory · Axiom Academy

FORMULA SHEET Graph Algorithms Reference Comprehensive quick-reference guide for all major graph algorithms with pseudocode, complexity, and key steps BREADTH-FIRST SEARCH (BFS) O(V + E) Initialize all vertices with distance ∞ Start with source vertex, set distance 0 Use queue for level-by-level exploration Mark each vertex when first discovered Process neighbors in FIFO order DEPTH-FIRST SEARCH (DFS) O(V + E) Color vertices: white (unvisited), gray (active), black (finished) Recursively explore as deep as possible Record discovery and finish times Produces DFS forest with tree/back/forward/cross edges DIJKSTRA'S SHORTEST PATH O((V + E) log V) Initialize distances to ∞, source to 0 Use min-heap to always process nearest vertex Relax edges: update if shorter path found Greedy: never revisit processed vertices Requires non-negative edge weights Relax all edges V-1 times (path can have at most V-1 edges) One more pass detects negative cycles Slower than Dijkstra but more general PRIM'S MINIMUM SPANNING TREE O((V + E) log V) Start with arbitrary root vertex Always add minimum-weight edge crossing cut Use min-heap to efficiently find next edge Similar to Dijkstra but minimizes edge weight, not path length KRUSKAL'S MINIMUM SPANNING TREE O(E log E) Initialize each vertex as separate set (disjoint-set data structure) Process edges in increasing weight order Add edge if it doesn't create cycle (connects different components) Use Union-Find for efficient cycle detection

This is the written version of the interactive lesson above. See the full Graph Theory course.