| 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(ElogV) |
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(EV) |