minimum-spanning-tree

10熱度

5回答

有向圖的雙向最小生成樹

給定具有加權邊的有向圖，可以使用什麼算法給出具有最小權重的子圖，但允許從圖中任何頂點移動到任何其他頂點（在假設任何兩個頂點之間的路徑總是存在的情況下）。這樣的算法是否存在？

3熱度

1回答

有關最小生成樹的快速問題

如果生成樹T0中的任何邊緣包含在某個最小生成樹T *中，是否意味着T0也是最小生成樹？現在，我試圖在紙上畫一些圖來證明它沒有。請糾正我，如果它確實，或者幫我找到一個例子，如果它不。在此先感謝。

1熱度

2回答

Java中的鄰接矩陣的最小生成樹

請幫助我理解如何從圖的鄰接矩陣中獲得最小生成樹！我用java編寫關於它的課程，截止日期是16.12.2010，但我覺得它會失敗。現在我的計劃可以：繪製節點繪製邊緣生成圖形的鄰接矩陣繪畫的地下室重邊的查找最小的邊緣連接到節點和有一些其他的測試/測試功能但我不知道如何實現Java中的Prim/Kruskal算法。我試圖找到一些決議在谷歌，但只找到Java-applet，需要工作.ob

1熱度

1回答

如何使用union-find，minheap，Kruskal's和排序算法來創建最小成本生成樹？（C++）

我很抱歉，如果這個問題有點寬泛，但我很難試圖瞭解如何創建一個最小成本生成樹。如果它很重要的話，這是用C++編寫的。根據我的理解，您將使用Kruskal's來選擇構建生成樹的最小成本邊。我的想法是把邊緣變成一個小堆，這樣你就可以從頂部移除，以便以最低的成本獲得邊緣。到目前爲止，我只能實現minheap並設置聯合發現，但我仍不確定聯合發現的目的以及創建生成樹的排序算法。我將不勝感激任何建議。編輯

0熱度

3回答

有向圖中的Prims和Bellman-Ford算法

請提供資源，以瞭解如何使用Prim算法在有向圖中找到最小生成樹，以及Bellman-Ford算法來計算有向圖中的最短路徑。

8熱度

2回答

最快最小生成樹算法

http://en.wikipedia.org/wiki/Minimum_spanning_tree 我期待我的基準最小生成樹對最好的最好的樹算法。有人知道我在哪裏可以找到這些算法的C++實現嗎？我瘋狂搜索並沒有發現任何東西。如果這些算法是最好的，肯定肯定有一個C++實現的地方？最快最小生成樹算法迄今被大衛·卡爾格，菲利普·克萊恩和羅伯特的Tarjan，誰發現基於Borůvka的算法和

3熱度

1回答

約束度+有界直徑最小生成樹的算法？

假設我有3種限制到計算生成樹：約束程度（例如：在的節點的生成樹可以僅連接到其他3個節點）界直徑（例如：所有邊的' 權重，一旦總和，不能超過 100）。 2.1。如果可能，請顯示符合此標準的所有子樹。兩個有沒有什麼好的算法來解決這個問題是不是要去開車送我瘋了嗎？我必須用相當大的插入點（1000多個節點）來運行它，所以它的複雜性也不能太高。

3熱度

1回答

Boruvka算法的複雜度如何可能爲O（E * logV）？

1 Begin with a connected graph G containing edges of distinct weights, and an empty set of edges T 2 While the vertices of G connected by T are disjoint: 3 Begin with an empty set of edges E 4 For

19熱度

3回答

更新當一個新的邊緣插入

我已經呈現在大學以下問題最小生成樹：讓G =（V，E）是（無向）圖與成本Ç e> = 0在邊緣e ∈ E。假定給你一個最低成本的生成樹T in G。現在假設一個新的邊緣被添加到ģ，連接兩個節點v，噸 v ∈ V成本Ç。給出一個有效的算法來測試是否Ť保持最小成本生成樹與新的邊緣添加到ģ（但不與樹Ť）。讓你的算法在O（| E |）的時候運行。你能在O（| V |）時間做到嗎？請注意您對於什麼數據結

0熱度

1回答

A *能夠放棄更好的路徑之後的非效率路徑嗎？

考慮A *算法。在谷歌有可能找到一個很好的僞代碼： function A*(start,goal) closedset := the empty set // The set of nodes already evaluated. openset := set containing the initial node // The set of tentative n