Most Important Graph Pattern Sheet: https://codolio.com/question-tracker/sheet/graph-mastery-sheet?category=topicspecific
| Problem | Algorithm | Pseudocode |
|---|---|---|
| Find Shortest Path in an Undirected Unweighted Graph from a source | BFS | queue.push(source) → while queue not empty → visit neighbors → mark visited |
| Find Shortest Path in a Directed/Undirected Weighted Graph (all edges ≥ 0) | Dijkstra’s Algorithm | minHeap.push((0, source)) → while heap not empty → relax edges → update distances |
| Find Shortest Path in a Directed/Undirected Graph with Negative Weights | Bellman-Ford Algorithm | Repeat (V-1) times: for each edge (u, v, w) → relax: dist[v] = min(dist[v], dist[u] + w) |
| Find Shortest Path Between Every Pair of Nodes (All-Pairs Shortest Path) | Floyd-Warshall Algorithm | for k in V: for i in V: for j in V: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) |
| Find Shortest Path with Multiple Visits Allowed | Intelligent BFS / Dijkstra Variant | BFS with state tracking (store extra params like remaining power, k turns, etc.) |
| Find Shortest Path in a Weighted Graph with 0-1 Weights | 0-1 BFS (Deque Optimization) | Deque.push_front if weight = 0, Deque.push_back if weight = 1 → process similar to Dijkstra |
| Problem | Algorithm | Pseudocode |
|---|---|---|
| Find a path starting from any node and visiting all vertices exactly once | Hamiltonian Path | Backtracking: try all paths, mark visited, backtrack when stuck |
| Find a cycle that visits every vertex exactly once and returns to the start | Hamiltonian Cycle (TSP related) | DFS with backtracking → if all visited and edge to start exists, return true |
| Find a path that visits every edge exactly once (Eulerian Path) | Hierholzer’s Algorithm | DFS-based → if degree conditions met, find Eulerian path via stack |
| Find a cycle that visits every edge exactly once (Eulerian Circuit) | Euler Circuit Algorithm | Same as Eulerian Path, but must return to start |
| Detect a cycle in an Undirected Graph | DFS / BFS with Parent Tracking | DFS → if neighbor is visited and not parent, cycle detected |
| Detect a cycle in a Directed Graph | DFS (Recursion Stack) or BFS (Topological Sort Failure) | DFS → if node is in recursion stack, cycle detected |
| Problem | Algorithm | Pseudocode |
|---|---|---|
| Find the Ordering of a Directed Graph with Dependencies | Topological Sort (Kahn’s Algorithm / DFS) | DFS → Postorder push to stack; BFS → use in-degree array |
| Find Strongly Connected Components (SCCs) in a Directed Graph | Kosaraju’s Algorithm / Tarjan’s Algorithm | Kosaraju: DFS + Reverse DFS; Tarjan: DFS + low-link values |
| Find Connected Components in an Undirected Graph | BFS / DFS | For each unvisited node → run DFS/BFS → count components |
| Check if a Graph is Bipartite | BFS / DFS with Two-Coloring | BFS → Assign alternating colors, if conflict → not bipartite |
| Find Bridges (Critical Connections) in a Graph | Tarjan’s Algorithm | DFS with discovery & low-link values → if low[v] > disc[u], bridge found |
| Find Articulation Points (Cut Vertices) in a Graph | Tarjan’s Algorithm | Similar to bridges but track child counts and root node cases |
| Problem | Algorithm | Pseudocode |
|---|---|---|
| Find a subset of the edges that forms a tree covering all nodes with minimum cost | Prim’s Algorithm / Kruskal’s Algorithm | Prim: Priority Queue (minHeap), Kruskal: Sort edges + DSU (Union-Find) |
| Find the Second Best MST | Kruskal’s Algorithm with Edge Exclusion | Find MST, then try removing each MST edge and recompute |
| Problem | Algorithm | Pseudocode |
|---|---|---|
| Find the shortest route that visits each city exactly once and returns to the start | Travelling Salesman Problem (TSP) | DP + Bitmasking (O(N² * 2^N)) or Approximation (Christofides Algorithm) |
| Find the Kth Shortest Path in a Graph | Modified Dijkstra with Heap (Yen’s Algorithm) | Run Dijkstra k times, maintaining multiple shortest paths |
| Find the Diameter (Longest Shortest Path) of a Tree | 2-pass BFS / DFS | Find farthest node from any node, then find farthest from that |
| Find the Maximum Flow in a Network Graph | Ford-Fulkerson Algorithm / Edmonds-Karp | Repeatedly push flow using BFS (Edmonds-Karp) or DFS |
| Find the Minimum Cut in a Graph | Max-Flow Min-Cut Theorem (Dinic’s Algorithm / Push-Relabel) | Same as max-flow but track min edges to disconnect source-sink |
| Problem | Algorithm | Pseudocode |
|---|---|---|
| Find if two nodes are in the same component (Dynamic Connectivity Check) | Union-Find (DSU) without Path Compression | Find: Keep going to parent until root; Union: Attach one tree to another |
| Optimized Union-Find (Path Compression + Union by Rank) | DSU with Path Compression + Union by Rank | Find: Flatten tree by pointing to root; Union: Attach smaller rank tree to larger |
| Find the number of connected components in a graph | DSU with Component Count | For each edge, union nodes; return unique root count |
| Detect a cycle in an Undirected Graph using DSU | DSU Cycle Detection | If two nodes of an edge belong to the same root → cycle exists |
| Find the Minimum Spanning Tree (MST) efficiently | Kruskal’s Algorithm (Uses DSU) | Sort edges → Add edge if it doesn’t form a cycle → Use DSU to check |
| Find Redundant Connection in a Tree (Extra Edge forming a cycle) | DSU with Edge Processing | For each edge, check if nodes already connected using DSU |