G-25. Find Eventual Safe States - BFS - Topological Sort

This comprehensive guide covers how to identify Eventual Safe States in a directed graph using Breadth-First Search (BFS) and Kahn's Algorithm (Topological Sort). We examine the structural intuition, graph reversal strategy, step-by-step trace, and complete production-ready code in both C++ and Java.

1. Problem Statement & Definitions

We are given a directed graph with $V$ vertices (indexed from $0$ to $V-1$) and $E$ edges.

• Terminal Node: A node with no outgoing edges (out-degree = $0$).
• Safe Node: A node is safe if every possible path starting from that node leads exclusively to a terminal node (or to another safe node that eventually terminates). If any path leads into a cycle or a dead-end that never terminates, the node is not safe.
• Goal: Return an array containing all the safe nodes of the graph, sorted in ascending order.

2. Why Do We Need a Topological Sort Approach?

In a previous lesson, this problem was solved using Depth-First Search (DFS) with cycle detection (visiting and path-visiting arrays). However, Topological Sort (Kahn's Algorithm) offers an intuitive alternative by working backward from terminal nodes.

The Core Obstacle:

Kahn's Algorithm naturally processes nodes with an in-degree of 0 (nodes with no incoming edges) and peels them away. But our problem defines safe starting points based on out-degrees (terminal nodes have an out-degree of 0).

The Genius Hack (Graph Reversal):

To bridge this gap, we reverse all the directed edges in the graph:

1. If an original edge went from u -> v, we flip it to v -> u.
2. Consequently, terminal nodes (which originally had an out-degree of $0$) now become nodes with an in-degree of $0$ in the reversed graph.
3. We can now run standard Kahn's Algorithm (Topological Sort via BFS) starting from these terminal nodes and propagate backwards through the reversed network.

3. Core Mental Model & Real-Life Analogy

Real-Life Analogy: Water Drainage in a Plumbing Network

Imagine a complex plumbing system where water flows through directed pipes.

• Terminals (Drains): Sinks or floor drains where water exits the system (out-degree = $0$).
• Safe Junctions: Any junction where all possible pipe routes eventually lead to a working drain. If even one pipe leads to a closed loop or stagnant pool, that junction is unsafe.
• Reversing the Pipes: Imagine pumping water backward from the drains. If a junction receives reverse flow and all its upstream dependencies are satisfied, we can verify it as a safe starting point.

4. Step-by-Step Algorithm Workflow

1. Reverse the Graph: Iterate through the adjacency list and reverse every edge (u -> v becomes v -> u). At the same time, compute the in-degrees for all nodes in this new reversed graph.
2. Initialize the Queue: Find all nodes in the reversed graph that have an in-degree of $0$ (these are our original terminal nodes) and push them into a BFS queue.
3. Perform BFS (Topological Peel):
   • Pop a node from the queue and record it as a safe node.
   • For each neighbor of this node in the reversed graph, decrement its in-degree by $1$ (representing the removal of an incoming dependency path).
   • If a neighbor's in-degree drops to $0$, push it into the queue.
4. Sort and Return: Collect all verified safe nodes, sort them in ascending order, and return the result.

5. Dry Run Walkthrough

Consider a graph where node 7 is a terminal node, pointing to 6, which points to 5 and 4.

6. Implementation Code (C++ & Java)

C++ Implementation

#include <vector>
#include <queue>
#include <algorithm>

class Solution {
public:
    vector<int> eventualSafeNodes(int V, vector<int> adj[]) {
        vector<vector<int>> adjRev(V);
        vector<int> indegree(V, 0);
        
        // Step 1: Reverse the graph and compute in-degrees
        for (int i = 0; i < V; i++) {
            for (auto it : adj[i]) {
                // Original: i -> it
                // Reversed: it -> i
                adjRev[it].push_back(i);
                indegree[i]++;
            }
        }
        
        // Step 2: Push all terminal nodes (indegree == 0) into the queue
        queue<int> q;
        for (int i = 0; i < V; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> safeNodes;
        
        // Step 3: BFS traversal (Topological Sort)
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            
            safeNodes.push_back(node);
            
            for (auto it : adjRev[node]) {
                indegree[it]--;
                if (indegree[it] == 0) {
                    q.push(it);
                }
            }
        }
        
        // Step 4: Sort the result in ascending order as requested
        sort(safeNodes.begin(), safeNodes.end());
        
        return safeNodes;
    }
};

Java Implementation

import java.util.*;

class Solution {
    public List<Integer> eventualSafeNodes(int V, List<List<Integer>> adj) {
        List<List<Integer>> adjRev = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adjRev.add(new ArrayList<>());
        }
        
        int[] indegree = new int[V];
        
        // Step 1: Reverse the graph and compute in-degrees
        for (int i = 0; i < V; i++) {
            for (int it : adj.get(i)) {
                adjRev.get(it).add(i);
                indegree[i]++;
            }
        }
        
        // Step 2: Push all terminal nodes (indegree == 0) into the queue
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < V; i++) {
            if (indegree[i] == 0) {
                q.add(i);
            }
        }
        
        List<Integer> safeNodes = new ArrayList<>();
        
        // Step 3: BFS traversal (Topological Sort)
        while (!q.isEmpty()) {
            int node = q.poll();
            safeNodes.add(node);
            
            for (int it : adjRev.get(node)) {
                indegree[it]--;
                if (indegree[it] == 0) {
                    q.add(it);
                }
            }
        }
        
        // Step 4: Sort the result in ascending order
        Collections.sort(safeNodes);
        
        return safeNodes;
    }
}

7. Complexity Analysis

8. Summary and Key Takeaways

• Terminal Node Definition: Nodes with an out-degree of $0$ are natural endpoints and form the baseline of safe states.
• Graph Reversal Strategy: Flipping directed edges (u -> v to v -> u) allows us to use standard Kahn's Algorithm (Topological Sort) starting from terminal nodes.
• In-Degree Tracking: In the reversed graph, terminal nodes start with an in-degree of $0$.
• Path Pruning: Removing edges during BFS simulates tracing backward from successful terminations; nodes whose dependencies cannot be fully resolved remain with non-zero in-degrees and are correctly excluded.
• Sorting Requirement: Always remember to sort the final resulting safe nodes array in ascending order before returning.
• Problem-Solving Diversity: Learning both DFS (cycle detection) and BFS (Topological Sort) approaches builds a robust mental toolkit for tackling complex directed graph problems.