Speed
500 ms
| Name | Time | Space | Graph | |
|---|---|---|---|---|
| Graph Traversal | ||||
| Depth First Traversal | O(V + E) | O(V) | All | |
| Breadth First Traversal | O(V + E) | O(V) | All | |
| Minimum Spanning Tree | ||||
| Prim's Algorithm | O((V + E) * log (V)) | O(V) | Undirected Weighted | |
| Kruskal's Algorithm | O(E * log (E)) | O(V) | Undirected Weighted | |
| Single Source Shortest Path | ||||
| Dijkstra’s Algorithm | O((V + E) * log E)) | O(V + E) | Directed Weighted | |
| Bellmon Ford | O(V * E) | O(V) | Directed Weighted | |
| All Pairs Shortest Paths | ||||
| Floyd Warshall | O(V3) | O(V2) | Directed Weighted | |
| Strongly Connected Components | ||||
| Tarjan's Algorithm | O(V + E) | O(V) | Directed | |
| Articulation Points / Cut Vertices | ||||
| DFS | O(V + E) | O(V) | Undirected | |
| Bridges / Cut Edges | ||||
| DFS | O(V + E) | O(V) | Undirected | |
| Cycle Detection | ||||
| DFS | O(V + E) | O(V) | Directed | |
| Kahn's Algorithm | O(V + E) | O(V) | Directed | |