改进寻找最小生成树的实现

Question

我正在尝试实现 Kruskal 的算法以在 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(vertices^2) 时间，当有多达 100,000 个顶点时，时间太长。

Answer 1

关键是要为你的集合使用合适的数据结构。合并节点集并测试任何两个节点是否在同一集中是一个经典的计算机科学问题，称为 "union-find"。

最好的数据结构很简单，在此处进行了描述：

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

使用此结构，您可以在几乎恒定的时间内合并集合并测试相等性，这使得您的 Kruskal 算法（您获得了预先排序的边列表）的实现几乎是线性的。

改进寻找最小生成树的实现

Improving Implementation of Finding a Minimum Spanning Tree

python

algorithm

graph-theory

minimum-spanning-tree

kruskals-algorithm