minimum-spanning-tree

1熱度

2回答

我已經分配了一個項目，我必須在一堆節點中，以及在某些節點之間加權的邊。我必須然後利用這些信息來找到一個最小生成樹爲圖中的每個連接元件（所以，如果有圖有兩個連接組件，我需要創建兩個生成樹）美中不足的是我不能使用任何STL庫除外。我知道我需要創建自己的數據結構，但我不知道我需要哪些數據結構。我想最小的堆將有助於找到要使用的最低重量邊緣，但是如何爲每個連接的組件創建最小堆？而我在想我需要實現聯合

2熱度

1回答

城市發電廠的最佳分配

我已經搜索谷歌和堆棧溢出爲我的問題的答案，但我找不到一個。我需要找到一個城市的電力網絡的最佳分配。城市由連通圖表示。我希望在其中一些節點之間分配發電廠，以覆蓋電網中的所有節點。問題在於每個發電廠都有一定的「範圍」（例如，它只能覆蓋兩個節點的「半徑」）。我的計劃需要找到覆蓋整個城市的最少數量的發電廠及其位置。我從我的搜索中知道它應該與MST（最小生成樹）有關，但問題在於發電廠的範圍有限。我想過

-1熱度

1回答

使用MST找到TSP的最有效上界

我很好奇最有效的方法是使用MST爲TSP找到最優（或接近最優）上限。我試圖優化我的算法以獲得速度，但是在找到MST後，我在算法上計算「好」界限時遇到了麻煩。我知道一個基地限制將是2 x MST length，但這似乎不是我們能做的最好的。任何參考或見解將不勝感激。

-1熱度

1回答

請幫助我使用Boost Graph Library

我想使用Boost Graph Library C++中的dense_boruvka_minimum_spanning_tree函數。我想要做的是生成一個隨機圖，然後將其輸入到該函數中並行運行Boruvka算法。任何人都可以通過幾行代碼來幫助我如何使用函數？

1熱度

4回答

連接一組頂點到最佳加權圖

這基本上與道路可能的最小量的連接n個目標的問題。的輸入是一組頂點（A，B，...，N）兩個頂點之間的邊的權重很容易計算（例子中的兩個頂點之間的距離笛卡爾）我想要一個給定一組頂點在歐幾里德空間中的算法，返回一組邊，這些邊將構成一個連通圖並且其邊的總權重儘可能小。在曲線圖的語言，這是一個連通圖的最小生成樹。用蠻力我會：定義的所有頂點之間的所有可能的邊緣 - 說你有n個頂點，那麼你有N（N

0熱度

1回答

確定一個TreeMap是否等於java中的一個映射

我正在編寫一個Prim算法用於派生最小生成樹的實現。我的圖形是一個Map<String, ArrayList>，其中他們的鍵對應於狀態名稱，值是指向兩個鏈接的指針的邊緣。 Prim的算法說我應該從一個只包含起始節點的樹開始循環，直到我的樹等於我的圖。我如何確定TreeMap<String, ArrayList>和Map<String, ArrayList>的等價性？

5熱度

3回答

在巨大的完整圖中找到MST的算法

讓我們假設一個> 25000個節點的完整圖。每個節點本質上是一個平面上的一個點。它有625M的邊緣。每條邊的長度都應該作爲浮點數存儲。我需要一種算法來找到它的MST（在通常的PC上）。如果我參加Kruskal算法，它需要所有的邊第一排序，但我買不起甚至完全在內存中同時存儲的邊緣。如果讓我選擇Prim算法，這是相當難以評估有多少邊緣將在同一時間被存儲在一個堆，但可能他們中的大多數將很快算法開

2熱度

2回答

查找權重僅爲1和2的生成樹的算法

給定每個邊上權重僅爲1和2的加權的，連通的簡單無向圖G，找到O中的G的MST（V + E）。任何想法？對不起，這個問題的措辭，我試着盡我所能翻譯它。

2熱度

2回答

使用Kruskal算法的最小跨越樹

我如何用Kruskal算法計算最小生成樹im R（3.0.0 - Linux x32）？我創建一個加權全圖用的igraph（0.6.5）庫作爲folws： set.seed(1234567890) g <- graph.full(n = 20) E(g)$weight <- round(runif(ecount(g)), 2) * 100 ，我能夠用普里姆（IGRAPH）到calcuta

0熱度

1回答

將新的邊添加到圖中並找到新的生成樹

假設我們給定了給定圖G（具有n個頂點和m個邊）和具有權重w的新邊e =（u，v）的最小生成樹T，我們將添加到G. I）檢查T是否仍然是MST。 II）如果不是，給出一個有效的算法來尋找圖G + e的最小生成樹。