0
$\begingroup$

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 ?

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.