有向グラフの最小スパン アーボレッセンスを返す JGraphX のメソッドはありますか?
getMinimumSpanningTree メソッドを使用して、「directed」パラメーターに「true」を設定しましたが、実際には Prim のアルゴリズムであり、一部の有向グラフで失敗します。
質問する
217 次
1 に答える
0
私の知る限り、JGraphX の機能セットはかなり限られています。これは、Mathematica とFindSpanningTreeという関数を使用して解決できます。デフォルトでは、最も適切な関数が選択されますが、必要に応じて、使用するメソッドをMinimumCostArborescenceに設定できます。
最小スパニング ツリーを見つけるには、次の 3 つのオプションがあります。
個人的には、ほとんどのグラフに Kruskal アルゴリズムを使用したいと思います。
Mathematica を使用するためにJLinkを設定するのは少しやり過ぎだと思う場合や無料のソリューションが必要な場合は、実行可能な無料のオープン ソースの代替手段として Python ライブラリSageがあります。Sage には、ジェネリック グラフの下にedge_disjoint_spanning_treesというメソッドがあります。
このオプションを好む場合は、java から python を呼び出す 5 つの方法を次に示します。
于 2015-01-05T10:09:35.227 に答える