kruskals-algorithm

0熱度

1回答

我一直在試圖解決類的問題。問題是：給定一個無向圖摹，發現摹內的最小生成樹。爲了通過這個問題，我的函數必須採取，並返回，一鄰接表。但是，我不確定如何去將輸入和輸出表示爲鄰接列表。 from collections import defaultdict class Graph: def __init__(self,vertices): self.V= vertices

0熱度

1回答

Networkx最小生成樹 - 精度問題？

我從222 x 222節點大小的加權鄰接矩陣創建圖。矩陣中給出的所有權重均爲0.42757498546089029和1.6671726002927263之間的浮點數。 nx.minimum_spanning_tree(G, weight = "weight")方法給了我下面的第一張圖片，同時如果我乘以所有矩陣值100.0同樣的方法給了我第二張圖片。在與igraph一樣繪圖時不會發生這種情況。 Ne

0熱度

1回答

在kruskal算法中對邊緣進行排序的最佳選擇？

我正在實施Kruskal的算法，我不確定什麼是更好的方式來訂購邊緣。我需要大輸入（300 000+邊）的最佳時間複雜度。我知道他們在時間複雜性上是相似的，但我想知道哪些更快的大輸入。

0熱度

1回答

如何檢查某個地區是否爲圓形？

所以，我有一個任務：使用克魯斯卡爾算法的修改將圖像分成區域，並確定其中哪些是圓圈並打印其半徑。找到區域比較簡單，我這樣做。不過，查找圈子很麻煩。我的想法是找到一個區域的所有邊界點，找到平均點 - 這個圓的可能中心 - 並計算每個邊界點和「中心」之間的距離。那麼，如果它們差別不大，那麼這確實是一個圓圈。首先，這是否可行？其次，這種方法也會將很薄的戒指識別爲圓圈，我不想那樣做。我該如何解決？ UP

2熱度

1回答

使特定節點的程度最小化的最小生成樹

我們如何找到使節點度數最小的最小生成樹v（在所有最小生成樹中）？會修改Kruskal算法，使得如果有幾個邊具有相同的重量，我們選擇不接觸的那個v解決問題？

0熱度

1回答

使用Kruskal算法計算最小生成樹時出現錯誤的答案

我正在嘗試使用kruskal算法來解決this MST question on spoj。我的程序似乎適用於所有的測試用例，但是反覆使用這個代碼會給WA帶來麻煩。我無法在此代碼上找到任何失敗的測試用例。有人能指出我做錯了什麼嗎？ import java.io.PrintWriter; import java.util.Arrays; public class CSTREET {

0熱度

1回答

Kruskal算法 - 修改爲矩陣數據結構？

這個版本的Kruskal算法代表了具有鄰接列表的邊緣。我該如何修改僞代碼來改爲使用鄰接矩陣？我在想你，我們就需要使用邊的權重爲實例（I，J），只要其不爲零。將頂點分配給i，j。我可能對這個Kruskals的僞代碼有點困惑。

-1熱度

1回答

Python OOP不相交集性能

我構建了一個與Kruskal的MST算法一起使用的不相交集數據結構。我需要加載並結合一個包含200k個互連節點的圖，我認爲我的數據結構實現是一個瓶頸。您有關於如何提高性能的建議嗎？我認爲我的查找方法可能有問題。 class partition(object): def __init__(self, element=None): self.size = 0 if

0熱度

1回答

在Python中實現Kruskal算法的錯誤輸出

我正在研究Krusal的算法。然而，我沒有得到正確的輸出。我不知道我在哪裏犯了錯誤。這裏是我的代碼： parent = dict() rank = dict() def make_set(vertice): parent[vertice] = vertice rank[vertice] = 0 def find(vertice): if parent[ve

1熱度

1回答

最小生成樹使用Kruskal算法

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