Find Eventual Safe States Using Topological Sort (BFS)

Problem Statement❯

In a directed graph with V vertices and E edges (represented as an adjacency list adj), each node is uniquely labeled from 0 to V - 1.

A node is called a terminal node if it has no outgoing edges. A node is a safe node if every possible path starting from that node eventually leads to a terminal node.

The task is to return a sorted list of all such safe nodes.

Examples❯

Adjacency List	Safe Nodes	Description
[[1,2],[2,3],[5],[0],[5],[],[]]	[2,4,5,6]	Only nodes that lead to terminal nodes (5 and 6) are safe
[[],[0,2,3,4],[3],[4],[]]	[0,1,2,3,4]	All nodes lead to terminal node 0 or 4
[[1],[2],[0]]	[]	Cycle exists, no node is safe
[[],[],[]]	[0,1,2]	All nodes are terminal and hence safe
[[],[0],[1]]	[0,1,2]	Each node leads to a terminal node

Solution❯

Understanding the Problem

In this problem, we are given a directed graph represented as an adjacency list. Our goal is to find all the eventual safe states.

An eventual safe state is a node from which any possible path will always lead to a terminal node (a node with no outgoing edges) and never enter a cycle. If a node can reach a cycle, it is not considered safe.

This means we must find all nodes that do not participate in or lead to a cycle in any way.

Step-by-Step Solution with Example

Step 1: Understand the graph structure

Let’s consider the example: graph = [[1,2],[2,3],[5],[0],[5],[],[]]

Each index represents a node, and the array at each index lists the nodes it points to. For instance, node 0 points to nodes 1 and 2.

Step 2: Reverse the graph

To track which nodes lead to which, we build a reversed graph. In the reversed graph, for every edge u → v in the original graph, we add an edge v → u.

This helps us track who depends on which node, making it easier to determine when a node becomes safe.

Step 3: Track out-degrees

We maintain an array where outdegree[i] stores the number of outgoing edges from node i in the original graph.

Terminal nodes (with no outgoing edges) will have outdegree 0. These are our starting point — they are trivially safe.

Step 4: Use a queue to process safe nodes

We put all terminal nodes in a queue and process them one by one. For each node removed from the queue, we go through its parents in the reversed graph and reduce their out-degree by 1.

If a parent’s out-degree becomes 0, it also becomes safe, so we add it to the queue.

Step 5: Collect and sort safe nodes

All nodes whose out-degree becomes 0 during this process are eventually safe. We collect them, sort them, and return them as the final answer.

Edge Cases

Empty graph: If the input graph has no nodes, the result should be an empty list.
All terminal nodes: If every node has no outgoing edges, all are safe.
All nodes in a cycle: If every node is part of a cycle, no node is safe.
Disconnected components: The algorithm handles each component independently. Safe nodes from different components are still detected correctly.

Finally

This problem is best understood by thinking in reverse: instead of finding which nodes can reach terminal states, we ask which nodes can be reached from terminal states without forming a cycle.

By reversing the graph and tracking out-degrees, we simulate a safe-state propagation, slowly marking each node safe once all its paths are known to be safe. This approach ensures an intuitive and efficient solution suitable even for large graphs.

Algorithm Steps❯

Reverse the graph: for each edge u → v, add u to revAdj[v].
Initialize an outDegree[] array where each element is the number of outgoing edges from a node in the original graph.
Create a queue and enqueue all nodes with outDegree = 0 (terminal nodes).
While the queue is not empty:

Dequeue a node node.
For each neighbor in revAdj[node]:

Reduce outDegree[neighbor] by 1.
If outDegree[neighbor] == 0, enqueue neighbor.

All nodes with outDegree == 0 at the end are safe. Return them sorted.

Code

JavaScript

function eventualSafeNodes(adj) {
  const V = adj.length;
  const revAdj = Array.from({ length: V }, () => []);
  const outDegree = Array(V).fill(0);

  // Step 1: Build reversed graph and count out-degrees
  for (let u = 0; u < V; u++) {
    for (const v of adj[u]) {
      revAdj[v].push(u);
      outDegree[u]++;
    }
  }

  const queue = [];
  for (let i = 0; i < V; i++) {
    if (outDegree[i] === 0) queue.push(i);
  }

  const safe = Array(V).fill(false);

  while (queue.length) {
    const node = queue.shift();
    safe[node] = true;
    for (const neighbor of revAdj[node]) {
      outDegree[neighbor]--;
      if (outDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  const result = [];
  for (let i = 0; i < V; i++) {
    if (safe[i]) result.push(i);
  }
  return result;
}

// Example usage:
console.log(eventualSafeNodes([[1,2],[2,3],[5],[0],[5],[],[]])); // Output: [2,4,5,6]

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(V + E)	Even in the best case (e.g., an acyclic graph), we must traverse all vertices and edges to identify safe nodes.
Average Case	O(V + E)	Each node and edge is visited once, whether it's part of a cycle or not.
Worst Case	O(V + E)	In graphs with deep chains or many dependencies, the traversal still touches all vertices and edges once.

Space Complexity❯

O(V + E)

Explanation: We store the reversed adjacency list, out-degree array, and queue, all of which depend on the number of vertices and edges.

⬅ Previous TopicCourse Schedule 2 - Task Ordering Using Topological Sort

Next Topic ⮕Alien Dictionary Character Order

Comments

Loading comments...