minimum-spanning-tree

0熱度

1回答

我有一個圖G =（V，E），其中有兩個權重函數w1（e）和w2（e），其中 w1（e）=（w2（e））^ 2。所有邊緣權重都是獨一無二的。在兩個權重函數下，Kruskal的算法將返回相同的最小生成樹。我知道kruskal是貪婪的，會選擇最短/最低成本的路徑。既然它們是肯定的，只要沒有成本爲1.5或者更低的路徑，我們最終會選擇相同的MST。在兩個權重函數下，Dijkstra的算法將返回相同的

1熱度

1回答

最小生成樹使用Kruskal算法

我使用Kruskal算法來完成確定後問題的最小生成樹的分配：我有個城市，而這一切都必須連接。我可以通過在它們之間修建道路或建造一個機場來連接它們。當我在城市建造一個機場時，它會連接到所有其他有機場的城市。我的疑問是，在未來的要求：在不止一個最佳的解決方案的情況下，我必須選擇一個具有較少的機場。我如何以最有效的方式保證這一點？

0熱度

1回答

陣列列表中的最小生成樹

我想知道是否有可能從ArrayList中找到最小生成樹。這是我目前有： import java.io.File; import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.Scanner; public class GraphReading { public static

-1熱度

1回答

如何利用普里姆算法找到如下圖的最小重量生成樹

Prim算法查找最小生成樹算法。首先選擇權重最小的任意邊緣，將其放入生成樹中。繼續向樹中已經存在的最小權重的樹邊添加樹，從不形成樹中已有邊的簡單電路。停止添加n - 1個邊。我知道你必須從節點A開始。同時給出一個列表中添加節點和/或邊的順序。但我不知道確切的步驟來找到最小權重生成樹。

-1熱度

1回答

有人能解釋如何的std ::更大的用於實現priority_queue

std::priority_queue<int, vector<int>, std::greater<int> > pq; 我不明白性病的工作::越大優先級隊列。我正在用優先級隊列替換minheap。此代碼取自 geeksForGeeks implementation of Prims algorithm using STL

1熱度

1回答

MST in unDirected graph

我有一個未排序的圖G =（V，E）和權重函數w：E→R +。我也有G的MST T. 我必須建立一個如下算法：如果我們添加一個具有權重w（e'）的新邊e'給E.建議一個算法它以新圖G'=（V，EUe'）的MST的方式更新T. 複雜度：O（V）。什麼我建議是： 1）添加E「到T.我們得到了一個新的圖形稱之爲T」，其中包括一個週期。 2）在T'上運行DFS並標記您訪問的每個頂點。並且另外保存堆棧中的

0熱度

1回答

Prims算法：圖論

下面是我的代碼爲Prims算法，我寫我自己的鏈表，因爲我已經被要求。它適用於較小數量的頂點，但是當頂點很大時它失敗（我得到812800作爲所有大數字的頂點的答案）。輸入格式：第一行有兩個整數，表示圖中的節點的數目和，表示在圖中的邊緣的數目。下一行每個由三個空格分隔的整數組成，其中和表示無向邊存在的兩個節點，表示相應節點之間的邊的長度。最後一行有一個整數，表示起始節點。如果同一對節點之間存

0熱度

1回答

如何在二維平面中找到連接一組座標的最小生成樹？

我已經在python中編寫了Prim的算法，但是這需要輸入帶有節點和邊的加權圖，這不是我所擁有的。如何將給定的座標轉換爲圖形，以便程序可以接受輸入，並且我得到一個有意義的答案？

0熱度

1回答

Prim算法的最壞情況圖

我的算法類正在討論Prim算法，作爲查找加權圖的最小生成樹的方法。我們的教授讓我們試着想一個Prim算法需要N^2次解決的圖的例子（N =頂點數）。班上沒有人能夠想到他們的頭頂，所以我問你。我很確定Prim的算法= O（N^2），所以這將是算法的最壞情況。什麼是Prim算法需要N^2個時間才能解決的圖的一個很好的例子？

-4熱度

1回答

關於最小生成樹圖

是否有比Prime更好的算法（更優化，更快）？Kruskal's algorithms？