Advanced Graphs Master Recap — Algorithm Selection Cheatsheet for FAANG Interviews

Problem Statement#

Given any advanced graph problem in an interview, identify the correct algorithm in under thirty seconds, state its time and space complexity, justify why it is the right choice over the alternatives, and start coding without second-guessing.

Constraints (covered across the chapter):

• Vertices 1 <= V <= 10^5
• Edges 1 <= E <= 5 * 10^5
• Edge weights may be negative for some problems
• Graphs may be directed or undirected, sparse or dense

Input:  problem statement plus a graph
Output: algorithm name, complexity, and a clean implementation

Why This Problem Matters#

The advanced graphs chapter is the longest and trickiest in any DSA prep plan because there are many algorithms and most of them look similar at first. Senior FAANG rounds frequently ask graph problems where the unspoken test is not coding speed but algorithm selection. A candidate who picks Floyd-Warshall when V is 10000 has already failed the interview, even if the implementation compiles.

This recap is the index to the chapter. After reading this once you should be able to look at any advanced graph problem and answer three questions immediately: which algorithm, what is the complexity, and what alternatives did I consider.

The recap is also a study tool. When you review before an interview, scan the algorithm selection guide first; the implementations themselves are easy to recall once the right algorithm is chosen.

The Core Insight#

Every advanced graph algorithm in the chapter falls into one of three families, and every problem maps cleanly onto a family by its recognition cue:

1. Greedy edge selection on weighted graphs: MST (Kruskal, Prim), max-flow min-cut (Edmonds-Karp, Dinic).
2. DFS with extra bookkeeping: SCC (Tarjan, Kosaraju), bridges, articulation points, topological sort, Eulerian paths.
3. Shortest-path relaxation: Dijkstra, Bellman-Ford, Floyd-Warshall, SPFA, A-star.

The ability to map a verbal problem statement onto one of these three families in seconds is the single most valuable skill in advanced graph interviews.

Visual Dry Run#

Solution (Optimal)#

class Solution:
    """Algorithm selection table for advanced graph problems.
 
    Use the cue column to map a verbal interview prompt onto an algorithm.
    Returned tuple is (algorithm name, time complexity, space complexity).
    """
 
    def select(self, cue: str) -> tuple[str, str, str]:
        table = {
            "min cost connect all":  ("Kruskal or Prim",        "O(E log E)",   "O(V)"),
            "scc":                   ("Tarjan SCC",             "O(V + E)",     "O(V)"),
            "bridges":               ("Tarjan bridges",         "O(V + E)",     "O(V)"),
            "articulation":          ("Tarjan AP",              "O(V + E)",     "O(V)"),
            "all pairs sp":          ("Floyd-Warshall",         "O(V cubed)",   "O(V squared)"),
            "sssp negative":         ("Bellman-Ford",           "O(V * E)",     "O(V)"),
            "sssp positive":         ("Dijkstra heap",          "O(E log V)",   "O(V)"),
            "heuristic":             ("A-star",                 "O(E log V)",   "O(V)"),
            "dag order":             ("Topological sort",       "O(V + E)",     "O(V)"),
            "use every edge":        ("Hierholzer Eulerian",    "O(E log E)",   "O(V + E)"),
            "max flow":              ("Edmonds-Karp",           "O(V * E^2)",   "O(V + E)"),
            "bipartite":             ("BFS 2-coloring",         "O(V + E)",     "O(V)"),
        }
        return table.get(cue, ("ask clarifying question first", "n/a", "n/a"))

var select = function(cue) {
    // Algorithm selection table mapping a verbal cue to a concrete algorithm.
    const table = {
        "min cost connect all": ["Kruskal or Prim",     "O(E log E)",  "O(V)"],
        "scc":                  ["Tarjan SCC",          "O(V + E)",    "O(V)"],
        "bridges":              ["Tarjan bridges",      "O(V + E)",    "O(V)"],
        "articulation":         ["Tarjan AP",           "O(V + E)",    "O(V)"],
        "all pairs sp":         ["Floyd-Warshall",      "O(V cubed)",  "O(V squared)"],
        "sssp negative":        ["Bellman-Ford",        "O(V * E)",    "O(V)"],
        "sssp positive":        ["Dijkstra heap",       "O(E log V)",  "O(V)"],
        "heuristic":            ["A-star",              "O(E log V)",  "O(V)"],
        "dag order":            ["Topological sort",    "O(V + E)",    "O(V)"],
        "use every edge":       ["Hierholzer Eulerian", "O(E log E)",  "O(V + E)"],
        "max flow":             ["Edmonds-Karp",        "O(V * E^2)",  "O(V + E)"],
        "bipartite":            ["BFS 2-coloring",      "O(V + E)",    "O(V)"],
    };
    return table[cue] || ["ask clarifying question first", "n/a", "n/a"];
};

Time: O(1) lookup per problem; the chapter's underlying algorithms range from O(V + E) up to O(V cubed) Space: O(1) lookup; underlying algorithms use O(V) to O(V squared) auxiliary memory

Common Mistakes#

• Reaching for Floyd-Warshall when V is large. The V cubed cost explodes past V around 500; run Dijkstra V times instead.
• Defaulting to Dijkstra when negative edges exist. Dijkstra silently produces wrong answers; switch to Bellman-Ford or SPFA.
• Picking Kruskal on a dense graph. Sort cost dominates; Prim with an array is O(V squared) which is faster when E is close to V squared.
• Running BFS for shortest path on a weighted graph. BFS minimizes hop count, not total weight.
• Forgetting that A-star degrades to Dijkstra when h equals zero, losing all goal-directedness.

Interview Tips#

• Memorize the recognition cue plus algorithm pair table. It is short and pays off across half the FAANG graph rounds.
• State the chosen algorithm and its complexity before writing code; this aligns you with the interviewer.
• Have Union-Find, Dijkstra, and topological sort templates internalized so you spend code time on the problem-specific logic.
• When in doubt between two algorithms, mention both and justify the pick by input shape (sparse vs dense, positive vs negative weights).
• Practice converting "minimum cost to connect", "find critical edges", and "shortest path with restrictions" prompts into algorithm names within ten seconds.

Follow-up Questions#

• When does Prim with a Fibonacci heap beat Prim with a binary heap? Hint: dense graphs where E is close to V squared, achieving O(E + V log V).
• How do you turn Floyd-Warshall into a path-recovery algorithm? Hint: maintain a parent matrix updated whenever a shorter path is discovered.
• How do you detect a negative cycle in Bellman-Ford? Hint: after V minus 1 relaxations any further relaxation indicates a negative cycle.
• Can you solve LC 332 Reconstruct Itinerary without Hierholzer? Hint: a backtracking DFS with sorted neighbors works at O(E log E) but is slower in worst cases.
• How would you parallelize Floyd-Warshall? Hint: each k-iteration only needs the previous matrix, so the inner i times j updates can be parallelized over rows or tiles.

Key Takeaways#

• Memorize the cue-to-algorithm map; it is the single highest leverage trick in advanced graph interviews.
• Three families cover the chapter: greedy edge selection, DFS with bookkeeping, shortest-path relaxation.
• Choose Kruskal for sparse graphs, Prim for dense graphs; both are correct via the cut property.
• Tarjan SCC, bridges, and articulation points share one DFS skeleton with disc and low arrays.
• Floyd-Warshall is the right tool for V less than 500 and many queries; otherwise prefer Dijkstra V times.
• Bellman-Ford handles negative weights and detects negative cycles in O(V times E).
• Always state the algorithm and its complexity before coding; pick the right tool first, write fast second.