Graphs
Traversal & shortest paths
Breadth-First Search
Explores a graph level by level using a queue — the backbone of shortest paths in unweighted graphs.
Time O(V + E) · Space O(V)
Depth-First Search
Dives as deep as possible along each branch before backtracking — implemented with recursion or a stack.
Time O(V + E) · Space O(V)
Dijkstra's Algorithm
Finds the shortest path from a source node to every other node in a weighted graph with non-negative edges.
Time O(V²) · Space O(V)
Bellman-Ford
Shortest paths from a source that also works with negative edge weights, by relaxing every edge V−1 times.
Time O(V · E) · Space O(V)
Topological Sort
Linear ordering of a DAG's nodes so every edge points forward — Kahn's algorithm peels off in-degree-0 nodes.
Time O(V + E) · Space O(V)
Prim's MST
Grows a minimum spanning tree from a start node, always adding the cheapest edge that reaches a new node.
Time O(V²) · Space O(V)
Kruskal's MST
Builds a minimum spanning tree by adding edges in weight order, using union-find to reject cycle edges.
Time O(E log E) · Space O(V)
A* Search
Best-first shortest path guided by a heuristic: expands the node with the lowest g + straight-line estimate.
Time O(E) · Space O(V)
Floyd-Warshall
All-pairs shortest paths by dynamic programming: round k asks every pair whether a stopover at node k shortens their path.
Time O(V³) · Space O(V²)