英文:
Guava Graph package: Method for testing if a undirected graph is a tree
问题
我想编写一个函数来测试无向图是否为树。到目前为止，我正在使用以下代码：
Function<Graph<Integer>, Double> targetFunction = g -> {
boolean isConnected = Graphs.reachableNodes(g, g.nodes().iterator().next()).equals(g.nodes());
return isConnected && Graphs.hasCycle(g);
};
Guava中是否已经有这个方法的实现（我没有找到）？如果没有，这个实现是否可以改进？
英文:
I want to write a function that tests if a undirected Graph is a tree.
So far, I'm using this:
Function<Graph<Integer>, Double> targetFunction = g -> {
boolean isConnected = Graphs.reachableNodes(g, g.nodes().iterator().next()).equals(g.nodes());
return isConnected && Graphs.hasCycle(g);
};
Is there already an implementation for this method in Guava (didn't find one) and if no, can this be improved?
答案1
得分: 0
你的实现存在两个问题。
g.nodes().iterator().next()返回图中的第一个节点 - 在这个图中是n1。假设该图是一棵树，n1可能不是树的根节点。因此，它可达的节点是所有节点的子集。hasCycle只会检测反向边，而不会检测正向边或交叉边。查看这个答案以了解其中的区别。
我无法从 guava 图形 API 中找到直接的解决方案。它只提供了对图数据结构、广度优先搜索和深度优先搜索的基本支持。
这个问题，确定有向或无向图是否为树，展示了如何实现你想要的算法。
英文:
Your implementation has two problems.
g.nodes().iterator().next()returns the first node -n1in the graph. Assume the graph is a tree,n1might not be the root of the tree. So its reachable nodes is a subset of all nodes.hasCycleonly detect back edges, but not forward edges or cross edges. Check the answer to find out the difference.
I cannot find a direct solution from guava graph api. It only provides basic support for graph data structure, bfs, and dfs.
This question, Determining whether or not a directed or undirected graph is a tree, shows how to implement what the algorithm you want.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论