Улучшение реализации поиска минимального связующего дерева

Я пытаюсь реализовать алгоритм Краскала, чтобы найти минимальное остовное дерево в Python для решения вопроса онлайн-судьи, но у меня возникают проблемы с ограничением времени. Вопрос дает серию ребер в порядке возрастания и спрашивает, возможно ли минимальное остовное дерево. Полные спецификации проблемы можно увидеть здесь.

Вот мой код проблемы:

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.


python algorithm graph-theory minimum-spanning-tree kruskals-algorithm
person Bob Marshall    schedule 27.10.2015    source источник
comment
Есть ли причина, по которой вы пишете свою собственную реализацию Kruskal вместо того, чтобы использовать уже написанную, например Scipy's minimum_spanning_tree ?   -  person jakevdp    schedule 27.10.2015
comment
@jakevdp Это потому, что судья не разрешает внешние библиотеки   -  person Bob Marshall    schedule 28.10.2015

Ответы (1)


arrow_upward
3
arrow_downward

Ключ в том, чтобы использовать соответствующую структуру данных для ваших наборов. Объединение наборов узлов и тестирование, чтобы увидеть, находятся ли какие-либо два узла в одном наборе, - это классическая задача информатики, называемая «объединение-поиск».

Лучшая структура данных для этого проста и описана здесь:

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

Используя эту структуру, вы можете объединять наборы и проверять на равенство в значительной степени за постоянное время, что делает вашу реализацию алгоритма Крускала (где вам предоставляется предварительно отсортированный список ребер) в значительной степени линейным.

person Matt Timmermans    schedule 27.10.2015