minimum-spanning-tree

0熱度

2回答

我目前正在學習C語言，並且最近編寫了一個程序來使用Prim算法找到最小生成樹。這個程序工作正常，但需要每個邊緣的成本（當然）。如果我想爲大量的2D座標（例如50）找到MST，我需要先找到點的歐幾里得距離矩陣。我的問題是：這可以在沒有計算的情況下在C中完成 distance = sqrt((x2-x1)^2+(y2-y1)^2) 對於每個單點，例如通過使用循環？我一直在嘗試使用 arrayX

2熱度

1回答

遞歸最小生成樹算法

這是尋找最小生成樹的正確算法。將圖劃分爲2個等同連接的部分。找到它最小的生成樹。用連接它們的最小邊連接它們。我試圖得到這個算法的反例，但是不能。

1熱度

2回答

什麼是最小葉生成樹？

有人可以解釋爲最小的葉子生成樹是什麼嗎？我很困惑，在生成樹中究竟是一片葉子。我知道生成樹包含簡單的沒有循環的路徑，它跨越圖G中的所有頂點，但是最小的葉是什麼？

0熱度

1回答

關於MST的一些問題

我現在正在學習最小生成樹的主題，並且我理解它的大部分內容，但是我仍然有一些我不明白的東西。我正在處理無向加權圖。首先，我知道找到MST花費O（E * log V）。現在，當我們處理平面圖時，我想優化它到線性時間 - O（V + E）。其次，我看到了單位平方中有n個點的例子，並且我成功地證明了存在權重爲O（sqrt n）的MST。問題是我找不到找到這個MST的算法。感謝所有，或者

0熱度

2回答

克魯斯卡爾算法如何貪婪？

據說Kruskal的MST構造算法是貪婪的，但算法選擇全局最小值而不是局部最小值，而不像Prim算法。有人可以解釋克魯斯卡爾算法是如何被認爲是一種貪婪的方法嗎？

0熱度

2回答

如何使用堆來優化Prim的最小生成樹算法？

我必須解決一個類似這樣的問題：我給了一個數字N來表示我擁有的點數。每個點具有兩個座標：X和Y 我能找到用下列公式兩個點之間的距離： ABS（X2-X1）+ ABS（Y2-Y1），（ x1，y1）爲第一點的座標，（x2，y2）爲第二點的座標，絕對值爲abs()。我必須找到最小生成樹，這意味着我必須讓所有的點與邊的總和最小。 Prim的算法很好，但它太慢了。我讀到，我可以使用heap使其更快，但

4熱度

1回答

查找MST的關鍵邊緣：可以使用修改後的Prim算法嗎？

我遇到了這個問題，同時找到了一個「關鍵邊」問題的解決方案。我已經解決的原始（C++）問題是：考慮圖G =（V，E）。查找有多少邊緣屬於全部 MST，有多少邊緣不是屬於任何 MST和有多少邊緣屬於某些MST，但不是全部。讓我們分別在上述三種情況下分別稱爲「綠色」，「紅色」和「黃色」邊緣。進行我的研究後，我遇到了Find all critical edges of an MST，它解決了這個問題

1熱度

2回答

Prim算法得到圖的最小生成樹

我需要Prim算法問題的一些幫助：設T是由Prim算法得到的圖G的最小生成樹。讓Gnew是通過添加至G新的頂點和配重一些的邊緣，新的頂點與G中一些頂點，我們可以通過添加新的邊緣T的一個構造Gnew的最小生成樹獲得的圖？如果你回答是，請解釋如何;如果不是，請解釋原因。預先感謝您！

2熱度

1回答

查找跨越給定的最小生成樹的最小權重完整圖形

讓T =（V，E）是|V|頂點樹和|E| = |V-1|邊，具有已知成本。我們要構建一個最小權重完整圖G =（V，E'）跨越牛逼其獨特的最小生成樹。示例：考慮以下樹T。紅色的邊緣有給定的成本。虛線邊將被添加以構造來自該樹的完整圖。最小重量完全圖摹跨越牛逼其獨特的MST如下：我試圖找到一個（多項式時間）算法來生成該圖。我期待的主要是小費，而不是完整的解決方案。到目前爲止，我已經設計了以下算法

0熱度

1回答

在Minimax路徑尋找解決方案中尋找路徑和最大稱量的邊緣？

我目前正在進行編程分配：給定大的加權無關圖（1 < V < 2000, E < 100000）。沿着從「源」到點「目的地」的最小加權路徑查找最大加權邊緣。到目前爲止我所得到的是將圖存儲在AdjacencyList（IntegerPair向量的向量中，其中第一個整數是鄰居，第二個是邊的權重）。我也用Prim算法獲得的最小生成樹： private static void process(int v