minimum-spanning-tree

0熱度

1回答

任何人都可以解釋我爲什麼下面不工作的代碼，並返回我 W = [.34 .34 ]; DG = sparse([1 2],[2 3],W); UG = tril(DG + DG') ???使用==>錯誤加上矩陣尺寸必須一致。下面的代碼能正常工作嗎？ W = [.34 .34 .34]; DG = sparse([1 2 3],[2 3 1],W); UG = tril(DG + D

3熱度

3回答

證明，沒有最小生成樹包含最大加權邊緣

比方說，有圖G，使得它的所有邊緣都對應於不同的整數權重。所以沒有兩個邊緣具有相同的重量。設E是G的所有邊。令emax爲E中具有最大權重的邊。 Graph G的另一個性質是每條邊e屬於G中的某個循環。我必須證明沒有G的最小生成樹包含邊emax。我不得不證明G的最小生成樹不包含邊emax。我明白爲什麼這是真的，因爲所有的邊是不同的，每邊屬於一個週期，最小生成樹算法可以簡單地選擇邊緣與包含EMAX周

1熱度

1回答

使用Prim算法從O（n^3）到O（n^2）優化MST

以下是我使用Prim算法將連通圖轉換爲MST的僞代碼。然而，我得到了n^3的複雜度，而不是n^2。請幫我弄清楚不需要的步驟。我有一個鄰接矩陣「a」來存儲圖邊的權重，一個2D矩陣「檢查」存儲樹中已經存在的頂點「1」，其餘的爲「0」。請注意，這也可以在nlog（n）中完成，但我不想引用任何現有的僞代碼，並希望自己嘗試。我將不勝感激優化我自己的方法的答案。 Initialize check. //ch

0熱度

2回答

最小產品生成樹是否與最小生成樹不同？

最小產品生成樹是否與最小生成樹不同？ PLZ解釋（如果可能的話，用示例）。我的意思是，添加到最小值的邊應該（？）也具有最小的乘積。

0熱度

1回答

爲MCST分配缺少的邊緣成本

我在解決舊的考試試卷時遇到了這個問題。根據所給出的選項，我幾乎不知道如何解決這個問題。考慮以下無向圖ģ一些邊成本丟失。假設虛線刃形成最小成本從生成樹（MCST）ģ。那麼下列哪個不等式需要而不是持有？成本（A，B）≥6 成本（B，E）≥5 成本（E，F）≥5 成本（A，d）≥4 成本（b，c）≥4

0熱度

2回答

有沒有什麼辦法可以快速找到無向/有向圖中的一個週期（後沿）的所有邊？

我有一個最小生成樹。我爲它添加了一個邊緣。當然會形成一個循環。我需要找到作爲該週期一部分的所有邊，即所有後邊。可以做多快？我的解決方案 - 例如，如果它是邊緣（1,4），請在所有位置向Adj（1）添加4，然後每次運行dfs。例如。如果Adj（1）有2,3,5，則在2之前先加4，運行DFS。我會得到回報。然後在2和3之間添加4並運行dfs。我得到了另一個後端。然後在3和5之間等等。有沒有更快的方法來

2熱度

1回答

java中最小生成樹（鄰接矩陣）

我有一個問題，我真的很苦惱。我有一組邊緣重的村莊，我需要創建一棵最小生成樹來找到最短路徑。我已經根據重量找到了村莊的最短路徑，我真的不知道該怎麼做我該如何執行這與鄰接矩陣？我會感謝任何幫助:) -10個村莊（節點）

3熱度

1回答

C++如何實現秩定理雙重量（而不是整數）

我發現使用Kruskal算法的最小生成樹模板here 他們使用整數重量，是可能的，如果我要實現的代碼使用雙重重量？我在這裏和那裏做了更改，並一直給我錯誤。這是我改變了：和 double myComp(const void* a, const void* b) { struct Edge* a1 = (struct Edge*)a; struct Edg

-3熱度

1回答

如何將Dijkstra算法應用到我的鄰接圖？

我有一個編程任務，需要我建立一個鄰接圖並應用Dijkstra算法來找到一個MST。我已經構建了我的鄰接圖，但是我不知道如何將僞代碼應用於Dijkstra算法。鏈接曾經爲Dijkstra算法爲鄰接表的代碼，http://www.cs.utsa.edu/~wagner/CS3343/newgraph/graphrep.html 僞代碼： http://i.imgur.com/TtPARzW.png

0熱度

2回答

圖形可視化

我寫了一個java程序，用隨機生成的100個頂點和隨機生成的800個邊來計算最小生成樹。我想繪製一下當我運行它時該程序生成的圖形。有誰知道任何工具，可以幫助這個？下面我的Java代碼： public static void main (String [] args) { Random random = new Random(); Edge[] edges = new Ed