Предварительное требование для графов для направленного ациклического графа

Question

Каждое дерево является направленным, ациклическим графом (DAG), но существуют DAG, которые не являются деревьями. a) Как мы можем определить, является ли данный DAG деревом? b) Разработать алгоритм для проверки того, является ли данная DAG деревом?

Answer 1

1. Убедитесь, что имеется ровно n - 1 края (где n является число вершин).

2. Убедитесь, что существует вершина с нулевым индексом.

3. Запустите глубину первого поиска из этой вершины и убедитесь, что все вершины достижимы из нее.

Если хотя бы одно из этих условий не выполняется, это не дерево. В противном случае это дерево.