Advanced Graphs — Complete Guide for FAANG Interviews (MST, SCC, Bridges, Floyd-Warshall, A-Star)

Problem Statement#

Given a graph problem more complex than plain BFS or DFS — minimum spanning tree, strongly connected components, all-pairs shortest paths, bridges, or heuristic search — choose the correct algorithm, implement it cleanly, and analyze its complexity.

Constraints (typical interview ranges):

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

Input:  Problem description plus a graph (V vertices, E edges)
Output: An algorithm name, a complexity bound, and a clean implementation

Why This Problem Matters#

Most candidates can recite BFS and DFS. Senior interview rounds at Google, Meta, Amazon and Microsoft go further: they probe whether you can recognize when basic traversal is not enough and reach for a specialized algorithm. Minimum spanning trees show up in network design and clustering. Strongly connected components appear in dependency analysis and 2-SAT. Bridges show up in critical-connection problems and network reliability. Floyd-Warshall and Bellman-Ford handle negative weights and dense all-pairs queries. A-star powers map directions and game pathfinding.

The advanced graph chapter is also where complexity reasoning gets tested seriously. Choosing Kruskal versus Prim, Floyd-Warshall versus repeated Dijkstra, or Bellman-Ford versus a topological sort on a DAG depends on the input shape (sparse vs dense, weighted vs unweighted, positive vs negative weights). Strong candidates explain the trade-off in one sentence before they write a single line of code.

This guide is the index for the rest of the chapter. Internalize the seven patterns and you will recognize 90 percent of advanced graph problems on first read.

The Core Insight#

Every advanced graph algorithm is a refinement of one of three general ideas: greedy edge selection (MST), DFS with extra bookkeeping (SCC, bridges, articulation points), or shortest-path relaxation (Dijkstra, Bellman-Ford, Floyd-Warshall, A-star). Recognizing which idea applies converts an unfamiliar problem into a routine one.

Pattern map:

Visual Dry Run#

Solution (Optimal)#

class Solution:
    # Kruskal with Union-Find for sparse minimum spanning tree problems.
    def kruskal(self, n: int, edges: list[list[int]]) -> int:
        edges.sort(key=lambda e: e[2])  # smallest weight first
        parent = list(range(n))
        rank = [0] * n
 
        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]  # path compression
                x = parent[x]
            return x
 
        def union(x: int, y: int) -> bool:
            rx, ry = find(x), find(y)
            if rx == ry:
                return False  # would form a cycle
            if rank[rx] < rank[ry]:
                rx, ry = ry, rx
            parent[ry] = rx
            if rank[rx] == rank[ry]:
                rank[rx] += 1
            return True
 
        cost, taken = 0, 0
        for u, v, w in edges:
            if union(u, v):
                cost += w
                taken += 1
                if taken == n - 1:
                    break
        return cost if taken == n - 1 else -1

var kruskal = function(n, edges) {
    // Sort edges by ascending weight; greedy picks safe edges first.
    edges.sort((a, b) => a[2] - b[2]);
    const parent = Array.from({ length: n }, (_, i) => i);
    const rank = new Array(n).fill(0);
 
    const find = (x) => {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]]; // path compression
            x = parent[x];
        }
        return x;
    };
 
    const union = (x, y) => {
        const rx = find(x), ry = find(y);
        if (rx === ry) return false;
        if (rank[rx] < rank[ry]) { parent[rx] = ry; }
        else if (rank[rx] > rank[ry]) { parent[ry] = rx; }
        else { parent[ry] = rx; rank[rx]++; }
        return true;
    };
 
    let cost = 0, taken = 0;
    for (const [u, v, w] of edges) {
        if (union(u, v)) {
            cost += w;
            if (++taken === n - 1) break;
        }
    }
    return taken === n - 1 ? cost : -1;
};

Time: O(E log E) for Kruskal, O(E log V) for Prim, O(V + E) for SCC and bridges, O(V cubed) for Floyd-Warshall, O(V times E) for Bellman-Ford Space: O(V + E) for adjacency, O(V) auxiliary for most algorithms, O(V squared) for Floyd-Warshall distance matrix

Common Mistakes#

• Defaulting to Dijkstra when an edge weight can be negative. Dijkstra silently produces wrong answers; switch to Bellman-Ford or SPFA.
• Running BFS for shortest path on a weighted graph. BFS only minimizes hop count, not total weight.
• Picking Floyd-Warshall when V is large. The V cubed cost explodes past V around 500 and you should run Dijkstra from each source instead.
• Using Kruskal on a dense graph where Prim with a heap or array would be faster.
• Forgetting that A-star requires an admissible heuristic; with an inadmissible heuristic the result can be suboptimal.

Interview Tips#

• State the recognition cue out loud. Saying "minimum cost to connect every node, this is MST" anchors your interviewer.
• Mention the trade-off when picking Kruskal versus Prim or Floyd-Warshall versus repeated Dijkstra. Show you weighed options.
• Always describe complexity before writing code; this prevents picking the wrong algorithm.
• Keep Union-Find ready as a separate helper. It appears in MST, redundant connection, and account merging problems.

Follow-up Questions#

• When would you prefer Prim with a Fibonacci heap over a binary heap? Hint: dense graphs where E is close to V squared.
• How does Tarjan SCC compare with Kosaraju in practice? Hint: same time complexity, Tarjan uses one DFS pass and is cache-friendlier.
• Can you detect a negative cycle without running Bellman-Ford to completion? Hint: yes, after V minus 1 relaxations any further relaxation indicates a negative cycle.
• How do you adapt Floyd-Warshall to recover the actual shortest path? Hint: maintain a parent matrix updated whenever a shorter path is discovered.
• Why does A-star degrade to Dijkstra when h equals zero? Hint: priority becomes only g(n) and the search loses its goal-directedness.

Key Takeaways#

• Advanced graph problems split into three families: greedy edge selection, DFS bookkeeping, and shortest-path relaxation.
• Choose Kruskal for sparse graphs and Prim for dense graphs; both produce a correct MST due to the cut property.
• Tarjan SCC, bridges, and articulation points all share the same disc and low DFS skeleton.
• Floyd-Warshall is the right tool for dense all-pairs queries when V is small; otherwise run Dijkstra V times.
• Bellman-Ford handles negative weights and detects negative cycles in O(V times E).
• A-star equals Dijkstra plus an admissible heuristic; with a good heuristic it expands far fewer nodes.
• Always state recognition cue plus complexity before coding; it shows interview maturity and avoids implementing the wrong algorithm.