prims-algorithm

6熱度

1回答

我正在使用一個鄰接矩陣，優先級隊列是數據結構。通過我的計算，複雜度是V^3 log V： While循環：V 檢查相鄰的頂點：V 檢查條目是否已經存在，並更新相同的隊列：V log v 但是，我到處讀到複雜度爲V^2 請說明。

0熱度

3回答

我想用C++和矩陣實現Prim的算法。這裏是我的問題： int node[] = {11, 11, 0, 11, 11, 11, 11, 11}; int nodeCon[8]; void generatePrims() { int cNode = 3; for (int i = 1; i <= 8; i++) { if (graph[cNode][i]

4熱度

4回答

在STL優先級隊列中實現decreaseKey隊列C++

我試圖實現Prim的算法，並且我需要爲優先級隊列（更新優先級隊列中的鍵值）使用decreaseKey方法。我可以在STL優先級隊列中實現嗎？如果有幫助，這是我下面的算法：每個頂點u在圖G的U至INFINITY SET鍵NIL的U 集父將源頂點的密鑰設置爲0 將隊列改爲優先隊列Q使用上述關鍵字在圖中的所有頂點而Q不空彈出頂點u與Q中最低鍵對於每個相鄰的頂點v u的做如果（v是仍然在Q）和

1熱度

1回答

爲升麻Jarnik算法最有效的數據結構

什麼是這其中有最高效的數據結構：邊列表鄰接表鄰接矩陣執行普里姆-Jarnik的算法，爲什麼？

0熱度

3回答

圖算法：Prim

我想知道圖G的任何最小生成樹是否可以通過在此圖上執行算法Prim來提供？ Prim算法給我們提供了所有可能的MST嗎？

0熱度

2回答

Prim和Kruskal的算法複雜度

給定一個帶有權重的無向連通圖。 w：E - > {1,2,3,4,5,6,7} - 意思是隻有7個砝碼可能。我需要使用O（n + m）中的Prim算法和O（m * a（m，n））中的Kruskal算法找到生成樹。我不知道如何做到這一點，真的需要一些關於如何權重可以幫助我在這裏的指導。

1熱度

1回答

以鄰接矩陣爲參數的Prim MST

我正在C中使用Prim MST，並且該功能需要一個鄰接矩陣。鑑於當然在A[i][j]的重量。假設我有一個前驅數組，跟蹤我迄今爲止發現的最小邊。 predecessor[u]=v {這也是最終MST} 現在我想修改當前A[i][j]矩陣和更改爲1 的權重即當邊緣（索引）的前身陣列中也存在。否則我將其更改爲零。我該怎麼做？這是我的解決方案： for (x....) for (y...)

3熱度

1回答

C＃迷宮代我自己的實現Prim算法的Bug

首先讓我爲大小道歉我會盡量設法準確地建立Prim算法是怎麼說在維基百科上的我摸索出之後保持這種儘可能小我的迷宮沒有建立起來。所以我試圖做同樣的想法，以適應我的迷宮，但我看到一個奇怪的錯誤，當我的遊戲開始它只是無法正常建立我的迷宮，我無法弄清楚，爲什麼這是偶爾發生的其他時候，它完美的作品，所以我有一個public Dictionary<int, Dictionary<int, MazeC

3熱度

1回答

Prim's和Kruskal算法

Prim's和Kruskal算法都生成最小生成樹。根據切割屬性，這些算法的樹的總成本將是相同的，但是這兩種算法有可能給出不同的MST具有相同的總成本，假設我們在面對多種選擇時按字母順序選擇它。例如，我們比較max（source，dest），對於邊A-> B和B-> C，我們比較A→B和B→B-。謝謝

1熱度

1回答

請詳細說明優先級隊列中的減少密鑰和提取最小值操作之間的關係

EXTRACT-MIN操作和DECREASE-KEY優先級隊列中的操作之間的關係是什麼？我在使用Prim算法的最小生成問題講座中遇到了這個問題。麻省理工學院教授refers to it at point 01:07:16 seconds in the video但我沒有得到它。有人可以幫我解決這個問題嗎？ P.S：對於我對優先隊列的理解，我感覺很舒服。