최소 스패닝 arborescence jgraphx

Question

JGraphX에서 유향 그래프의 최소 스패닝 Arborescence를 반환하는 메서드가 있습니까?

'directed'매개 변수에 'true'를 설정하는 getMinimumSpanningTree 메서드를 사용하고 있지만 실제로 일부 유도 된 그래프에서는 실패하는 Prim의 알고리즘입니다.

Answer 1

내가 아는 한 JGraphX는 기능이 제한되어 있습니다. Mathematica와 함수 FindSpanningTree을 사용하여 이것을 풀 수 있습니다. 기본적으로 가장 적합한 함수를 선택하지만 원하는 경우 메서드을 MinimumCostArborescence에 사용하도록 설정할 수 있습니다.

• Prim
• Kruskal
• Minimum Spanning Arborescence

는 개인적으로 내가 가장 그래프의 크루스 칼 알고리즘을 선호 :

는 3 가지 옵션이 최소 스패닝 트리를 찾을 수 있습니다.

Mathematica를 사용하기 위해 JLink을 설정하는 것이 약간 과잉이거나 무료 솔루션을 원한다면, 실행 가능한 무료 오픈 소스 대안은 Python 라이브러리 Sage 일 것입니다. Sage는 일반 그래프에서 edge_disjoint_spanning_trees이라는 메서드를 사용합니다.

이 옵션을 선호하는 경우 java에서 파이썬을 호출하는 5 가지 방법이 있습니다. link.