| Algorithm | Time Complexity | Description |
|---|---|---|
| BFS | O(V + E) | Traverses the graph level by level. |
| DFS | O(V + E) | Explores as deep as possible before backtracking. |
| Algorithm | Time Complexity | Description |
|---|---|---|
| Dijkstra | O((V + E) log V) | Single-source shortest path using a priority queue. |
| Bellman-Ford | O(VE) | Finds shortest paths from a single source, handles negative weights. |
| A* | O(ElogV) | Optimized for heuristic-based pathfinding. |
| Floyd-Warshall | O(V³) | Finds shortest paths between all pairs of nodes. |
| Johnson | O(V² log V + VE) | Handles negative weights for all pairs shortest paths. |
| Algorithm | Time Complexity | Description |
|---|---|---|
| Kruskal | O(E log E) | Greedy algorithm using edge sorting and a disjoint set to avoid cycles. |
| Prim | O((V + E) log V) | Greedy algorithm using a priority queue to grow the MST incrementally. |
| Algorithm | Time Complexity | Description |
|---|---|---|
| Tarjan | O(V + E) | DFS-based algorithm for finding SCCs. |
| Kosaraju | O(V + E) | Uses two passes of DFS to find SCCs. |
| Algorithm | Time Complexity | Description |
|---|---|---|
| Kahn | O(V + E) | Iterative algorithm for ordering directed acyclic graphs. |
| Algorithm | Time Complexity | Description |
|---|---|---|
| Edmonds-Karp | O(VE²) | Finds maximum flow using BFS for augmenting paths. |