Loading...
Loading...
Loading Curriculum...
Loading Subject...
Loading Topic...
Loading Lesson...
Loading Lab...
A comprehensive guide to the time and space complexity of fundamental graph algorithms. Understanding these bounds is essential for selecting the optimal approach based on the size and density of your input data.
Most basic traversals are linear O(V+E), while complex pathfinding involving edge weights or multiple pairs scales quadratically or cubically.
For sparse graphs (E ≈ V), linear algorithms shine. For dense graphs (E ≈ V²), the overhead of priority queues (log V) becomes significant.
| Algorithm | Category | Time | Space |
|---|---|---|---|
| BFS / DFS | Traversal | O(V + E) | O(V) |
| Dijkstra | Shortest Path | O(E log V) | O(V) |
| Bellman-Ford | Shortest Path | O(V × E) | O(V) |
| Floyd-Warshall | All-Pairs | O(V³) | O(V²) |
| Kruskal / Prim | MST | O(E log E) | O(V + E) |
| Tarjan's SCC | Connectivity | O(V + E) | O(V) |
| Topological Sort | DAG | O(V + E) | O(V) |