Most tutorials stop at BFS and DFS. That’s fine for a junior role. But if you are interviewing for a top-tier product company or a routing-heavy startup (like Uber or DoorDash), the interviewer will push you further.
- “What if the roads have negative costs?” (Bellman-Ford)
- “How do we connect all cities with the cheapest wire?” (MST)
- “What if I remove this server, does the whole network crash?” (Bridges)
This guide is your Encylopedia. We have categorized the 12 Essential Graph Algorithms you must know to call yourself a Graph Master.
Category 1: Graph Traversals (The Foundation)
Before you calculate anything, you need to know how to walk.
1. Breadth First Search (BFS)
- Concept: Explore neighbor-by-neighbor (Level order).
- Best For: Shortest Path in Unweighted Graphs.
- Complexity: O(V + E)
2. Depth First Search (DFS)
- Concept: Explore as deep as possible, then backtrack.
- Best For: Detecting Cycles, counting Islands, verifying connectivity.
- Complexity: $O(V + E)$
Category 2: Shortest Path Algorithms (The GPS)
How do I get from A to B with the minimum cost/time?
3. Dijkstra’s Algorithm
- The Scenario: You have a map with different road lengths (weights). Weights are always positive.
- The Logic: Greedy approach using a Min-Heap. Always pick the closest unvisited node.
- Complexity: O(E log V)
4. Bellman-Ford Algorithm
- The Scenario: Same as Dijkstra, but some roads give you time back (Negative Weights). Dijkstra fails here.
- The Logic: Relax all edges V-1 times. It can also detect negative cycles (if cost reduces on the V-th iteration).
- Complexity: O(V times E) (Slower, but handles negative weights).
5. Floyd-Warshall Algorithm
- The Scenario: You need the shortest path between every pair of nodes (A to B, C to D, X to Y) all at once.
- The Logic: Dynamic Programming. “Can I go from i to j faster by going through k?”
- Complexity: O(V^3) (Only for small graphs, V < 400).
Category 3: Minimum Spanning Tree (The Network Builder)
Connect all computers/cities with the least amount of cable. No cycles allowed.
6. Prim’s Algorithm
- The Strategy: “Grow a tree.” Start from one node. Always add the cheapest edge that connects a visited node to an unvisited one.
- Data Structure: Min-Heap.
- Best For: Dense Graphs (lots of edges).
7. Kruskal’s Algorithm
- The Strategy: “Connect the edges.” Sort all edges by weight. Add them one by one unless they form a cycle.
- Data Structure: Union-Find (Disjoint Set).
- Best For: Sparse Graphs (fewer edges).
Category 4: Directed Acyclic Graphs (The Scheduler)
Planning tasks where A must happen before B.
8. Topological Sort (Kahn’s Algorithm)
- The Scenario: “Find a valid order to compile these files” or “Course Schedule.”
- The Logic: Count dependencies (Indegree). Process nodes with 0 dependencies first.
- Complexity: O(V + E)
Category 5: Connectivity & Structure (The Architect)
Analyzing the structural integrity of the graph.
9. Union-Find (Disjoint Set Union – DSU)
- The Scenario: “Group these friends into circles.” “Are A and B connected?”
- The Logic: Path Compression + Rank optimization. Almost O(1) operations.
- Complexity: O(alpha(V)) (Inverse Ackermann function – nearly constant).
10. Bridges & Articulation Points
- The Scenario: “Critical Connections.” If I remove this edge (Bridge) or this node (Articulation Point), does the graph break into two pieces?
- The Logic: Use DFS with
discovery_timeandlowest_reachable_time. - Interview Level: Hard (Google/Meta favorite).
11. Tarjan’s / Kosaraju’s Algorithm
- The Scenario: Finding Strongly Connected Components (SCC). In a directed graph, finding groups where every node can reach every other node in that group.
- The Logic: Uses two passes of DFS (Kosaraju) or one smart pass (Tarjan).
Category 6: The “Advanced” Bonus
Only for competitive programming or specific Hard interviews.
12. A Search (A-Star)*
- The Scenario: Pathfinding in games or maps where you have a heuristic (an estimate of distance to target).
- The Logic: Dijkstra + Heuristic function. It’s faster because it “aims” toward the destination.
The “Master Teacher” Summary Table
Stick this table at the bottom of your post. It is the perfect revision tool.
| Algorithm | Type | Best Used For… | Time Complexity |
| BFS | Traversal | Shortest Path (Unweighted) | O(V+E) |
| DFS | Traversal | Connectivity / Cycles / Mazes | O(V+E) |
| Dijkstra | Shortest Path | Weighted Graph (Positive) | O(E log V) |
| Bellman-Ford | Shortest Path | Negative Weights / Detect Neg Cycle | O(VE) |
| Floyd-Warshall | Shortest Path | All-Pairs Shortest Path | O(V^3) |
| Prim’s | MST | Minimum Wire Cost (Dense Graph) | O(E log V) |
| Kruskal’s | MST | Minimum Wire Cost (Sparse Graph) | O(E log E) |
| Topo Sort | DAG | Task Scheduling / Dependencies | O(V+E) |
| Union-Find | Set | Dynamic Connectivity / Cycles | O(V alpha(V)) |
| Tarjan/Kosaraju | Connectivity | Strongly Connected Components | O(V+E) |
| Bridges | Structure | Critical Edges (Network Failure) | O(V+E) |
The Ultimate Graph Algorithms Roadmap: From Zero to Google-Ready (2026 Guide)
Graph Algorithms List , Dijkstra vs Bellman Ford vs Floyd Warshall, Minimum Spanning Tree Prim Kruskal, Detect Cycle in Directed Graph,
“Students, don’t panic. You don’t need to memorize the code for all 12.
- Must Code: BFS, DFS, Dijkstra, Union-Find. (Daily Usage)
- Must Understand Logic: Bellman-Ford, Topo Sort, MST. (For Tricky Questions)
- Good to Know: Bridges, Floyd-Warshall. (For Hard Interviews)”
YouTube Channels:
Trendy VS Vlogs
VS Coding Academy
Join Our WhatsApp Channel for the latest job opportunities and updates:
VS_CODING_ACADEMY WhatsApp Channel
Join Our Telegram Channel for the latest job opportunities and updates: https://t.me/vscodingacademy
Open our site in Telegram Bot: https://t.me/vscodingacademy_bot
For DSA Guide: https://vscodingacademy.com/category/dsa-guide/