Advanced Graph Algorithms

Go beyond BFS and DFS. Master Flow Networks (Max-Flow Min-Cut), Strongly Connected Components (Tarjan’s), and Eulerian Paths to optimize flow & scale.

1. The Hook: Optimizing Flow

Shortest path is about latency. Max Flow is about throughput. If you are designing a pipeline, a traffic network, or a logistics chain, you don’t care how fast one car gets there; you care how many cars can arrive per hour.

Key Insight (Max-Flow Min-Cut Theorem): The maximum amount of flow possible from source to sink is equal to the capacity of the bottleneck cut that separates them.

---

2. Strongly Connected Components (SCC)

In a Directed Graph, if you can get from A → B AND from B → A, they are strongly connected. A SCC is a maximal subset of vertices where every vertex is reachable from every other vertex in the subset.

Use Case: Cycle detection in build systems, finding “communities” in social networks.

Algorithms:

1. Kosaraju: Two DFS passes (Forward + Transpose). O(V+E).
2. Tarjan: One DFS pass using low-link values. O(V+E).

---

3. Eulerian Path & Circuit

• Eulerian Path: Visit every Edge exactly once.
• Hamiltonian Path: Visit every Vertex exactly once.

Eulerian Path Exists If:

1. Graph is connected (ignoring isolated vertices).
2. Count of vertices with odd degree is 0 or 2.

Hamiltonian Path: NP-Complete. No efficient algorithm exists!

---

4. Implementation: Tarjan’s SCC

Java

Go

// Simplified Tarjan's Algorithm logic
public void tarjan(int u) {
  stack.push(u);
  onStack[u] = true;
  ids[u] = low[u] = id++;

  for (int v : adj.get(u)) {
    if (ids[v] == -1) {
      tarjan(v);
      low[u] = Math.min(low[u], low[v]);
    } else if (onStack[v]) {
      low[u] = Math.min(low[u], ids[v]);
    }
  }

  // Root of an SCC found
  if (ids[u] == low[u]) {
    while (!stack.isEmpty()) {
      int node = stack.pop();
      onStack[node] = false;
      low[node] = ids[u];
      if (node == u) break;
    }
    sccCount++;
  }
}

// Simplified Tarjan's Algorithm logic
func tarjan(u int) {
  stack = append(stack, u)
  onStack[u] = true
  ids[u] = id
  low[u] = id
  id++

  for _, v := range adj[u] {
    if ids[v] == -1 {
      tarjan(v)
      if low[v] < low[u] {
        low[u] = low[v]
      }
    } else if onStack[v] {
      if ids[v] < low[u] {
        low[u] = ids[v]
      }
    }
  }

  // Root of an SCC found
  if ids[u] == low[u] {
    for {
      node := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      onStack[node] = false
      low[node] = ids[u]
      if node == u {
        break
      }
    }
    sccCount++
  }
}

---

5. Deep Dive Strategy Lab: Advanced Graphs

Intuition Through Analogy

Max Flow is like water pipes. The total water coming out of the tap cannot exceed the width of the thinnest pipe in the wall. That thinnest pipe is the Min-Cut. Finding the Min-Cut tells you exactly where to invest money to upgrade the system.

Mathematical Anchor: Flow Conservation

For any node u (except Source s and Sink t): Σ f_in(u) = Σ f_out(u) Input Flow = Output Flow. Nothing is created or destroyed inside the network.