java - ルートとリーフを指定してグラフからツリーを取得する

Question

jgrapht と jung の両方を見ていますが、やりたいことを実行できる方法が見つからないようです。

グラフがあり、ルート ノードといくつかの葉を指定して、そこからツリーを取得するか、それが不可能な場合は少なくともエラーを取得したいと考えています。

jgraphT と jung の両方が、グラフから最小スパニング ツリーを取得するためのアルゴリズムを持っているようですが、取得されたツリーはランダムであり、特定のノードがリーフになり、別のノードがリレーになるとは誰も保証しません....

Answer 1

リーフが 1 つだけの問題を考えると、「ルートから始まり、他のすべてのノードを少なくとも 1 回訪問するリーフで終わるウォークがあるか?」という質問に発展します。

これは、最長パス問題に非常によく似ています...これは NP 困難です。（そして、葉を追加しても効果はないと思います。:)）

ヒューリスティックなアプローチ (および特定のグラフ、またはルート/リーフの選択について、問題に解決策がないことを証明する方法) を考えることができますが、一般的には、徹底的な検索アプローチを使用する必要があると思われます。このようなもの：

1. 葉からすべての発信エッジを削除します。
2. ルートからすべてに到達できない場合 (ここでは BFS が行います)、解決策はありません。
3. ルートからグラフのトラバースを開始します。
4. 各ステップ:
   すべての葉に到達しておらず、通過するエッジがこれ以上ない場合、解決策はありません。すべてのリーフに到達し、すべてのノードにアクセスしたら、完了です。
   それ以外の場合は、まだ通過していないエッジを通過します。