Guava Graph包：测试图是否为树的方法

Question

我想编写一个测试图是否为树的函数。到目前为止，我正在使用此：

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

Guava中是否已经有此方法的实现（找不到），如果没有，可以改进吗？

Answer 1

您的实现有两个问题。

• g.nodes().iterator().next()返回图形中的第一个节点-n1。假设图形是一棵树，n1可能不是树的根。因此其可达节点是所有节点的子集。
• hasCycle仅检测后边缘，而不检测前边缘或交叉边缘。检查the answer找出差异。

我无法从番石榴图api找到直接的解决方案。它仅提供对图形数据结构，bfs和dfs的基本支持。

此问题Determining whether or not a directed or undirected graph is a tree，说明了如何实现所需的算法。