CODEWITHSUNDEEP
algorithm
user3754566
user3754566

Reputation: 11

Smallest subet of nodes that reach all nodes in DAG

Say we have a DAG comprised of a list of nodes A, B, C, D, and E.

Each node has a list of reachable nodes - for example:

A --> B, C
A --> B
D --> E

In this case, we would have to visit nodes A and D to comprehensively visit all nodes in the graph. What is the best algorithm to approach this problem in general?

Upvotes: 1

Views: 160

Answers (2)

Photon
Photon

Reputation: 2777

Here is a linear approach:

  1. For every node count it`s in-degree (number of edges pointing to it)
  2. Because graph is a DAG (no cycles) we can just take all nodes with in-degree of 0 as our starting sub-set

Time Complexity(N + M) - linear in graph size

Upvotes: 2

oybek
oybek

Reputation: 650

Here is an approach.

Let's say that node A is parent of node B if there is an arc from A to B. And node C is the most-parent of node B, if it has no parent and there is a path from C to B.

  1. Mark every node as not visited.

  2. For every node in DAG you define it's parent.

  3. for every node A that is not visited

    1. Find A's most-parent MP

    2. Mark all nodes that are reachable from MP as visited

    3. Put MP to array

After this you'll get smallest subset of nodes that reach all nodes in DAG in array

Time compexity of algo is O(n^2)

Upvotes: 1

Related Questions