edge = [[1,2,1],[1,2,3],[1,3,2],[2,3,1],[2,4,4],[3,4,2]]
#這是用邊集合表示的圖
s = [[]]
n = 4
for i in range(n):
s.append([i+1])
#print s
#compare方法是為了對邊排序寫的,作為參數傳入sort,就可以排序了
def compare(a,b):
if(a[2] > b[2]):
return 1
elif(a[2] < b[2]):
return -1
else:
return 0
edge.sort(compare)
#這就是sort()的厲害之處
for e in edge:
# print s
if s[e[0]] != s[e[1]]:
print e
for i in s[e[1]]:
if(i not in s[e[0]]):
s[e[0]].append(i)
s[e[1]] = s[e[0]]
其中涉及到集合的合并和比較。