{x}
blog image

All Ancestors of a Node in a Directed Acyclic Graph

You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive).

You are also given a 2D integer array edges, where edges[i] = [fromi, toi] denotes that there is a unidirectional edge from fromi to toi in the graph.

Return a list answer, where answer[i] is the list of ancestors of the ith node, sorted in ascending order.

A node u is an ancestor of another node v if u can reach v via a set of edges.

 

Example 1:

Input: n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
Output: [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
Explanation:
The above diagram represents the input graph.
- Nodes 0, 1, and 2 do not have any ancestors.
- Node 3 has two ancestors 0 and 1.
- Node 4 has two ancestors 0 and 2.
- Node 5 has three ancestors 0, 1, and 3.
- Node 6 has five ancestors 0, 1, 2, 3, and 4.
- Node 7 has four ancestors 0, 1, 2, and 3.

Example 2:

Input: n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Output: [[],[0],[0,1],[0,1,2],[0,1,2,3]]
Explanation:
The above diagram represents the input graph.
- Node 0 does not have any ancestor.
- Node 1 has one ancestor 0.
- Node 2 has two ancestors 0 and 1.
- Node 3 has three ancestors 0, 1, and 2.
- Node 4 has four ancestors 0, 1, 2, and 3.

 

Constraints:

  • 1 <= n <= 1000
  • 0 <= edges.length <= min(2000, n * (n - 1) / 2)
  • edges[i].length == 2
  • 0 <= fromi, toi <= n - 1
  • fromi != toi
  • There are no duplicate edges.
  • The graph is directed and acyclic.

Solution Explanation: Finding All Ancestors in a Directed Acyclic Graph (DAG)

This problem asks us to find all ancestors for each node in a directed acyclic graph (DAG). An ancestor of a node is any node that can reach the given node through a series of directed edges. The solution presented uses Breadth-First Search (BFS).

Algorithm:

  1. Adjacency List Construction: The input edges array represents the graph's structure. We first create an adjacency list representation of the graph. This list, denoted as g, stores for each node i, a list of all nodes directly reachable from i (its successors).

  2. BFS for each node: The core of the algorithm involves iterating through each node in the graph (from 0 to n-1). For each node i, we perform a BFS starting from node i.

  3. BFS Traversal and Ancestor Recording: The BFS explores all nodes reachable from i. As the BFS visits each node j reachable from i, we add i to the list of ancestors of j (ans[j]). This list ans stores the ancestors for each node, initialized as an empty list for every node.

  4. Output: Finally, the algorithm returns ans, a list where ans[i] contains the sorted list of ancestors of node i.

Time Complexity Analysis:

  • The adjacency list construction takes O(E) time, where E is the number of edges.
  • The outer loop iterates n times (for each node).
  • The BFS for each node in the worst case visits all nodes, resulting in O(V) time complexity, where V is the number of nodes (n). However, since we're using an adjacency list, in practice, this will be closer to O(E) rather than O(V^2) as it would be with an adjacency matrix.
  • Therefore, the overall time complexity is O(n * (V+E)), which simplifies to O(nE) if we assume E > V (more edges than vertices which is typical for dense graphs) or O(nV) if we assume V > E. This is effectively O(n^2) in the worst case if the graph is dense (E is proportional to V^2), but for sparse graphs, it's often closer to O(nE).

Space Complexity Analysis:

  • The adjacency list g requires O(V+E) space.
  • The ans list takes O(n) space to store the results (in the worst-case, all nodes could be ancestors of a single node. In a sparse graph it could be far less).
  • The queue used in BFS takes O(V) space in the worst case.
  • Thus, the overall space complexity is O(V+E), which is equivalent to O(n+E).

Code Examples (Python, Java, C++, Go, TypeScript, C#):

The provided code snippets in multiple languages follow this algorithm accurately. Each one demonstrates the adjacency list creation, the BFS function, and the overall loop structure to collect ancestor information for each node. They differ only slightly in syntax and data structure handling (using defaultdict in Python, ArrayList in Java, vector in C++, slices in Go, arrays in TypeScript, and Lists in C# to represent lists). The BFS implementations are all structurally similar, employing a queue to manage the nodes to be visited.

Note: The assumption of a Directed Acyclic Graph (DAG) is crucial. The algorithm's correctness relies on the absence of cycles. If cycles existed, the BFS might run indefinitely.