Guava Graph package: метод для проверки, является ли неориентированный граф деревом

Question

Я хочу написать функцию, которая проверяет, является ли неориентированный граф деревом.
Пока я использую это:

Function<Graph<Integer>, Double> targetFunction = g -> {
    boolean isConnected = Graphs.reachableNodes(g, g.nodes().iterator().next()).equals(g.nodes());
    return isConnected && Graphs.hasCycle(g);
};

Уже есть реализация этого метода в Гуаве (не нашел), и если нет, можно ли это улучшить?

Answer 1

Ваша реализация имеет две проблемы.

• g.nodes().iterator().next() возвращает первый узел - n1 на графике. Предположим, что граф является деревом, n1 может не быть root дерева. Таким образом, его достижимые узлы являются подмножеством всех узлов.
• hasCycle обнаруживает только задние края, но не передние края или поперечные края. Проверьте ответ , чтобы узнать разницу.

Я не могу найти прямое решение из API-интерфейса guava graph. Он обеспечивает только базовую c поддержку структуры данных графа, bfs и dfs.

Этот вопрос, Определение того, является ли направленный или ненаправленный граф деревом , показывает, как реализовать какой алгоритм вы хотите.