Graph
| Algorithm | time complexity (worst) | time complexity (typical) | space complexity | restriction | notes |
|---|---|---|---|---|---|
| DFS | V + E | V + E | V + E | Graph with adjacency sets | recursive alg |
| BFS | V + E | V + E | V | Graph with adjacency sets | BFS computes a shortest path |
| DFS connected components |
V(V + E) | V(V + E) | V + E | Graph | for each V, run a DFS, store connectivity in a size V array |
| BFS shortest path |
V + E | V + E | V + E | Graph | one pass of BFS, need a queue to store edges. |
| DirectedDFS | V + E | V + E | V + E | Directed graph with adjacency sets | exam E adjacency-list entry once, recursive func have 1 or 2 instant variables |
| DirectedBFS | V + E | V + E | V | Directed graph with adjacency sets | max queue size is V |
| Topological order | V + E | V + E | V + E | no restriction | one DFS to detect circle + reverse postorder DFS |
| KosrajuScc | V + E | V + E | V + E | any digraph | reverse digraph + 2 DFS |
| DirectedCycle | V(V + E) | V(V + E) | V + E | Graph | worst case, it runs a DFS for each vertex V |
| Lazy Prim | ElogE | ElogE | E | MST | priority queue |
| Eager Prim | ElogV | ElogV | V | MST | priority queue with index |
| Kruskal | ElogE | ElogE | E | MST | priority queue and union-find |
| Dijkstra (Eager Prim) | ElogV | ElogV | V | SPT with positive edges | worst-case guarantee |
| topological sort | E + V | E + V | V | SPT with DAG | relaxing vertices in topological order |
| Bellman-Ford (FIFO based) |
E + V | VE | V | no negative circles | general case: each of the V passes relaxes E edges. FIFO: work on edges that changed in the last pass only |
In the above table, the time and space complexity is listed for various graph algorithms. All the cost calculation are abased on these most important facts -- for adjacency set implementation of graph with V vertexes and E edges:
- the space is V + E
- add edge v-w cost logV
- check w is adjacent to v cost logV
- iterate the vertices adjacent to v cost logV + degree(v)
