Advanced Graphs — Complete Guide (MST, SCC, Bridges, Floyd-Warshall, A*)

Beyond BFS/DFS — Advanced Graph Patterns

Pattern 1 — Minimum Spanning Tree

Connect all V vertices with V-1 edges of minimum total weight.

Kruskal's: Sort edges by weight, use Union-Find to add edge if it doesn't form a cycle.

Prim's: Greedy from any vertex, always pick minimum-weight edge crossing the cut.

Pattern 2 — Strongly Connected Components (SCC)

A SCC is a maximal set of vertices where every vertex is reachable from every other.

Tarjan's: Single DFS with disc[], low[], and a stack. Node is SCC root when low[u] == disc[u].

Kosaraju's: Two DFS passes. First on original graph (record finish order), then on transposed graph in reverse finish order.

Pattern 3 — Bridges and Articulation Points

Bridge: Edge whose removal disconnects the graph. low[v] > disc[u] for edge u→v.

Articulation point: Vertex whose removal disconnects the graph. Two conditions: root with 2+ children, or non-root with low[v] >= disc[u].

Pattern 4 — All-Pairs Shortest Path

Floyd-Warshall: DP over intermediate vertices. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for each k.

Detects negative cycles: dist[i][i] < 0 after running.

Pattern 5 — A* Search

Like Dijkstra but with a heuristic h(n) estimating distance to goal. Priority = g(n) + h(n).

Must be admissible (never overestimates) for correctness. Manhattan distance for grids.

Union-Find Template (for Kruskal)

class UF:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0]*n
    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x])
        return self.par[x]
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        if self.rank[px] < self.rank[py]: px, py = py, px
        self.par[py] = px
        if self.rank[px] == self.rank[py]: self.rank[px] += 1
        return True