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

Question

我正在查看 jgrapht 和 jung 但我似乎找不到任何方法可以让我做我想做的事。

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

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

Answer 1

如果您只考虑一个叶子的问题，那么这会转移到问题“是否存在从根开始并在叶子结束且至少访问每个其他节点一次的遍历？”

这听起来很像最长路径问题……这是 NP 难题。（而且我不认为添加更多的叶子有帮助。:)）

我可以想到启发式方法（以及证明特定图或根/叶选择的方法，该问题没有解决方案），但我怀疑通常您将不得不使用详尽的搜索方法，像这样的东西：

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