改進查找最小生成樹的實現

我想實現克魯斯卡爾的算法來找到一個Python中的最小生成樹來解決在線裁判的問題，但我遇到了時間限制問題。這個問題以遞增的順序給出了一系列邊，並詢問是否可以使用最小生成樹。全部問題規格可以看出here.改進查找最小生成樹的實現

這裏是我的問題代碼：

import sys 
raw_input = sys.stdin.readline 
line = map(int, raw_input().split()) 
n = line[0] 
m = line[1] 
dict1 = {} 
lists = [] 

for i in xrange(1, n + 1): 
    dict1[i] = set([i]) 

for i in xrange(m): 
    edge = map(int, raw_input().split()) 
    a = edge[0] 
    b = edge[1] 
    if dict1[a] != dict1[b]: 
     newSet = dict1[a].union(dict1[b]) 
     for vertice in newSet: 
      dict1[num] = newSet 
     lists.append(i + 1) 

check = all(dict1[x] == dict1[1] for x in dict1.keys()) 

if check: 
    for i in lists: 
     print i 
else: 
    print "Disconnected Graph"

代碼首先創建獨立集合所有可能的頂點。然後，對於每個邊，它檢查兩個頂點所在的集合是不同的。如果是，那麼這兩套與工會運作結合在一起。組合集合中的每個頂點都是新創建的組合集合的成員。如果頂點已經連接，則它們被跳過。我覺得我的代碼的問題是時代的套在了線進行更新的數量：

for vertice in newSet: 
    dict1[num] = newSet

是否有更新設置，以檢查它們是否相等更快的方法？此操作大約需要O（頂點^ 2）時間，並且在有多達100,000個頂點時需要很長時間。

來源

2015-10-27 Bob Marshall

是否有任何理由要編寫自己的Kruskal實現，而不是使用已經寫入的實現（例如， [Scipy's'minimum_spanning_tree'']（http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html）？ – jakevdp

@jakevdp這是因爲法官不允許外部庫 –

關鍵是要爲您的套件使用適當的數據結構。合併節點集合和測試以查看是否有任何兩個節點在同一集合中，這是一個稱爲「聯合發現」的經典計算機科學問題。

這樣做的最好的數據結構是容易的，這裏描述：

http://www.algorithmist.com/index.php/Union_Find

採用這種結構，可以在幾乎恆定的時間，使您的克魯斯卡的實施合併集和測試平等算法（其中提供了預先排序的邊緣列表）幾乎是線性的。

來源

2015-10-27 01:18:00

改進查找最小生成樹的實現

回答

相關問題