سؤال

I have a homework assignment that I've completed, and about 3 points out of 100 are for the following question.

"Suppose you construct a DFS tree on a directed graph. Afterwards you notice that there aren't any back edges. What does this say about the graph?"

I've given this some thought and all I can reason is that this means there is implied dependency such that only one specific path exists to topologically traverse through the graph. Unfortunately I have not been able to find any information about this anywhere on the web, so I thought I'd post my answer here and see if anyone could weigh in on its (in)correctness. Please let me know if you have any additional thoughts or pointers that might help me out with this problem.

Thanks a bunch!

هل كانت مفيدة؟

المحلول

In any directed graph, if DFS does not report back edges, then the graph does not have cycles.

نصائح أخرى

Perhaps there is a more nuanced answer, but my immediate thought is that it implies there are no cycles in the graph.

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top