Java：使用JGraphT生成最小生成樹？

Question

我有一個問題，基本上可以看作一個圖。我正在考慮使用JGraphT來實現它，而不是滾動我自己的。使用JGraphT從圖中獲得最小生成樹的最佳方法是什麼？

Answer 1

不幸的是，我不知道足夠的圖論給你一個完整的，直接的答案，但我已經在幾個項目中使用jgrapht，所以也許這會有所幫助。

包含jgrapht是這裏的算法列表：http://www.jgrapht.org/javadoc/org/jgrapht/alg/package-summary.html，你還可以找到圖遍歷實現迭代器（如果這是任何幫助）在這裏：http://www.jgrapht.org/javadoc/org/jgrapht/traverse/package-summary.html

我敢肯定，沒有這些算法將讓你想要開箱即用，所以你必須自己編寫代碼，但我可以從經驗告訴你，在jgraph之上編寫代碼而不是從頭開始更容易。還有一個FibonacciHeap類，可能有助於實施Prim的算法。

如果您需要算法本身的幫助，有許多關於維基百科條目的算法，包括詳細的描述和僞代碼。 Minimum spanning tree article鏈接到他們。

Answer 2

Jung有一個這樣的實現。

Answer 3

ClosestFirstIterator可能會幫助你。它在遍歷頂點時使用FibonacciHeap構建生成樹。

ClosestFirstIterator提供方法getShortestPathLength（）和getSpanningTreeEdge（）來獲取最小生成樹的部分。

// instantiate the iterator 
ClosestFirstIterator<V,E> it = new ClosestFirstIterator<V,E>(graph, start_vertex); 

// iterate to build the tree 
while(it.hasNext()) 
    it.next(); 

// query 
double distance = getShortestPathLength(vertex); 
E next_edge = getSpanningTreeEdge(vertex);