Graph Algorithms

Graph algorithms depend on direction, weights, density, and representation. Read graph representations before this section.

Problem	Common algorithm	Preconditions	Typical time
Reachability / unweighted distance	BFS	Unweighted graph	Θ(V + E)
Structural traversal	DFS	None	Θ(V + E)
Dependency order	Topological sort	Directed acyclic graph	Θ(V + E)
Single-source shortest paths	Dijkstra	Non-negative weights	O((V + E) log V)
Negative-weight shortest paths	Bellman–Ford	No reachable negative cycle for finite answers	O(VE)
Minimum spanning tree	Kruskal / Prim	Weighted undirected graph	commonly O(E log V)

Bounds assume adjacency lists where appropriate. A disconnected graph requires a forest traversal or produces a minimum spanning forest rather than one tree.