java通过指定根和叶从图形中获取树

Question

我正在研究jgrapht和jung，但我似乎没有找到任何方法让我做我想做的事情

我有一个图，通过指定一个根节点和一些叶子，我想从中获得一棵树，或者至少是一个错误（如果不可能）

jgraphT和jung似乎都有alghoritms从图中获得最小生成树，但得到的树是随机的，没有人向我保证给定的节点是一片叶子，另一个是中继

Answer 1

如果你只考虑一片叶子的问题，那么这就变成了一个问题：“是否有一个从根部开始并在至少每一次访问其他节点的叶子结束的散步？”p>

这听起来很像最长路径问题。。。这是NP难的。（我不认为增加更多的叶子有什么帮助。：）

我可以想到启发式方法（以及证明特定图形或选择根/叶的方法，证明问题没有解决方案），但我怀疑一般情况下，您将不得不使用穷举搜索方法，类似这样的方法：

1. 从叶子上移除所有外边缘
2. 如果您不能从根目录访问所有内容（BFS将在此处完成），则没有解决方案
3. 从根开始遍历图形
4. 每一步：
   如果还没有到达所有的叶子，并且没有更多的边可以遍历，那么就没有解决方案。 如果你已经到达了所有的叶子，并且所有的节点都被访问了，那么你就完成了
   否则，请遍历尚未遍历的边