Определение того, является ли ориентированный или неориентированный граф деревом

Мне бы хотелось узнать о быстром алгоритме, позволяющем определить, является ли ориентированный или ненаправленный граф деревом.

Этот пост, кажется, имеет дело с этим, но это не очень ясно; по этой ссылке, если граф ацикличен, то это дерево. Но если вы рассмотрите ориентированные и ненаправленные графы ниже: по моему мнению, только графы 1 и 4 являются деревьями. Я полагаю, 3 не является ни циклическим, ни деревом.

enter image description here

Что необходимо проверить, чтобы увидеть, является ли направленный или ненаправленный граф деревом или нет, эффективным способом? И на шаг впереди: если дерево существует, то является ли оно бинарным или нет?

Ответы

Ответ 1

Для ориентированного графа:

  • Найти вершину с только исходящими ребрами (если их больше или нет),

  • Сделайте BFS или DFS из этой вершины. Если вы столкнулись с уже посещенной вершиной, это не дерево.

  • Если вы закончили и есть неисследованные вершины, это не дерево - граф не подключен.

  • В противном случае это дерево.

  • Чтобы проверить бинарное дерево, дополнительно проверьте, имеет ли каждая вершина не более двух исходящих ребер.

Для неориентированного графа:

  • Проверьте цикл с простым поиском глубины (начиная с любой вершины) - "Если неисследованный край приводит к ранее посещенному node, тогда график содержит цикл." Если есть цикл, это не дерево.

  • Если вышеприведенный процесс оставляет неиспользуемые вершины, это не дерево, потому что оно не связано.

  • В противном случае это дерево.

  • Чтобы проверить бинарное дерево, дополнительно проверьте, что все вершины имеют 1-3 ребра (один для родителя и 2 для детей).

    Проверка для корня, то есть ли одна вершина содержит 1-2 ребра, не требуется, поскольку в ациклическом связанном неориентированном графе должны быть вершины с 1-2 ребрами.

    Обратите внимание, что идентификация корня в общем случае невозможна (это возможно в особых случаях), поскольку во многих неориентированных графах более одного из узлов можно сделать корнем, если мы хотим сделать это двоичным деревом.