graph-algorithmslisted

# Graph Algorithm Patterns Graph problems appear frequently in competitive programming and technical interviews. The key challenge is recognizing which technique fits the problem structure. This reference covers eight core patterns with recognition heuristics, templates, and pitfall guides. --- ## Pattern Recognition Table | Trigger Signals | Technique | Typical Complexity | |---|---|---| | Shortest path, unweighted, fewest steps | BFS | O(V + E) | | Explore all paths, connected components, backtracking | DFS | O(V + E) | | Shortest path, weighted (non-negative) | Dijkstra | O((V + E) log V) | | Dependencies, ordering, DAG | Topological Sort | O(V + E) | | Dynamic connectivity, "are X and Y connected?" | Union-Find (DSU) | O(alpha(N)) per op | | Minimum cost to connect all nodes | MST (Kruskal/Prim) | O(E log E) | | Weighted shortest path with negative edges | Bellman-Ford | O(V * E) | | Two groups, coloring, odd cycle | Bipartite Check | O(V + E) | --- ## Constraint-to-Technique Mapping Use V (vertices) and E (edges) bounds to narrow viable algorithms: | Constraint Range | Viable Techniques | Notes | |---|---|---| | V <= 20 | Bitmask DP, brute-force BFS/DFS | Exponential OK | | V <= 1,000, E <= 10,000 | All techniques, Floyd-Warshall for APSP | O(V^3) still feasible | | V <= 100,000, E <= 200,000 | BFS, DFS, Dijkstra, Topo Sort, DSU, MST | Standard competitive range | | V <= 1,000,000 | BFS, DFS, DSU, Kahn's | Avoid O(V log V) heaps if possible | | Negative weights p