| Unweighted Graph |
Breadth First Search (BFS) |
Explore each adjacent node before moving to next level(s) |
Queue |
O ( E + V ) |
| Directed Acyclic Graph (DAG) (positive and negative edge weights) |
Topological Sorting and Bellman Ford |
Edge relaxation in topological order |
Stack |
O ( E + V ) |
| Directed Graph with only positive edge weights |
Dijkstra’s Algorithm C++ Python Java |
C++ / Java : Extract the closest node(extract min) stored in a set / priority queue. O(VlogV), for each neighbor relax the edge and update the heap. O ( E log V ) |
Heap |
O((E+V)logV) |
| Directed Graph with positive and negative edge weights |
Bellman Ford |
For all the nodes (V), relax all the edges (E) |
List |
O ( E . V ) |