Search code examples
algorithmgraph-algorithmdirected-acyclic-graphsancestor

What exactly are ancestors in DAG

I am new to graph theory and confused with ancestors definition in DAG(or in general graph).

For example in the following DAG

1--->2--->3<---4<---5

If I start DFS from 1 vertex first then path covered is 1--2--3. Then next if I start DFS from vertex 5, then the path covered is 5--4. Vertex 3 is not visited again. So visited order is 1 2 3 5 4.
What about the ancestors of 3. Are they only 1,2 or 4,5 also ? what about ancestor Ancestor of 4. Is it only 5 or 1,2 also as they were also visited before visiting 5 ?

Solution

  • The ancestors of a vertex v in a DAG is the set of all vertices v' != v such that v is reachable from v'. So in your example, the ancestors of 3 would be 1, 2, 4 and 5.

    Of course it's different if you are just looking at a particular path: so the ancestors of 3 in the path 1->2->3 would just be 1 and 2.