Полувнешний Крускал: рёбра на диске, компоненты в памяти

Если механизм уже знаком - листай до «Теперь сам».

Как думаешь: что нужно сохранить

Граф содержит десятки миллионов рёбер, но относительно немного вершин. Нужно ли помещать в память весь граф, чтобы построить остов? В момент обработки очередного ребра Крускалу нужны его вес, два конца и ответ «уже связаны?». Списки смежности всех прочих рёбер в этот момент не используются. Значит, граница памяти проходит не там, где кажется по размеру полного входного файла.

На что это похоже

Представь длинную очередь предложений построить дороги. Предложения лежат в папках на складе, а на столе - небольшой список текущих объединений городов. После сортировки по цене ты просматриваешь предложения по одному. Принятая дорога меняет объединения; отклонённое предложение можно сразу забыть. Хранить все папки на столе незачем.

Механизм: от определения к алгоритму

Пусть в графе n вершин и m рёбер. Полувнешний алгоритм хранит Θ(n) состояния в оперативной памяти, а потенциально гораздо больший массив рёбер - во внешней. Union-find содержит родителя и ранг или размер для каждой вершины. Для ребра (u,v) найди представителей; если они различны, объедини и выдай ребро в остовный лес. Если граф несвязен, итогом будет минимальный остовный лес, а не ошибка алгоритма.

Во внешней модели с блоком B и памятью M внешняя сортировка стоит Sort(m) вводов-выводов; для обычного режима это O((m/B) log_(M/B)(m/B)) с нижней границей одного прохода. Сканирование добавляет O(m/B). Union-find работает в памяти за почти линейное процессорное время O(n + m α(n)): инициализация массивов для всех n вершин сама требует Θ(n), даже если рёбер мало. Эти процессорные операции нельзя объявлять дисковыми обращениями, пока массив компонентов действительно помещается в M.

Если даже union-find не помещается, наивные find вызывают случайные обращения на диск, и доказанная полувнешняя оценка перестаёт действовать. Тогда нужны сжатие графа, внешние приоритетные очереди или другой внешний алгоритм. Само слово «Крускал» не устраняет ограничение по вершинам.

Фильтрующий Крускал разбивает рёбра по весовому порогу. Сначала рекурсивно обрабатывает лёгкую часть. После этого тяжёлое ребро, чьи концы уже связаны лёгкими рёбрами, можно удалить: оно замыкает цикл и не понадобится выбранному остову. Оставшиеся тяжёлые рёбра обрабатываются рекурсивно. У равных весов используй фиксированный вторичный ключ, если нужен воспроизводимый конкретный остов; минимальный суммарный вес не требует единственности решения.

Фильтрация способна уменьшить сортируемую тяжёлую часть, но не гарантирует уменьшения на каждом экземпляре. На почти древесном графе мало циклов и нечего отбрасывать. Оценка полувнешнего сканирования и выигрыш фильтра по входным данным должны обсуждаться раздельно. Обычная сортировка в программе ниже - только модель внешней сортировки.

Правило

Внешне сортируй и последовательно сканируй рёбра, пока union-find целиком в памяти; фильтруй тяжёлое ребро лишь после обработки лёгких рёбер, доказавших связность его концов.

Разбор: проследим вычисление

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

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
    def join(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] > self.size[b]:
            a, b = b, a
        self.parent[a] = b
        self.size[b] += self.size[a]
        return True

edges = [(1, 0, 1), (2, 1, 2), (3, 2, 3),
         (20, 0, 2), (30, 0, 3), (40, 1, 3)]
plain = DSU(4)
answer = [e for e in sorted(edges) if plain.join(e[1], e[2])]
print('обычный вес', sum(e[0] for e in answer))

dsu = DSU(4)
light = [e for e in edges if e[0] <= 3]
heavy = [e for e in edges if e[0] > 3]
chosen = [e for e in sorted(light) if dsu.join(e[1], e[2])]
remaining = [e for e in heavy if dsu.find(e[1]) != dsu.find(e[2])]
print('тяжёлых до фильтра', len(heavy), 'после', len(remaining))
for edge in sorted(remaining):
    if dsu.join(edge[1], edge[2]):
        chosen.append(edge)
assert sum(e[0] for e in chosen) == sum(e[0] for e in answer)
print('фильтрующий вес', sum(e[0] for e in chosen))

обычный вес 6
тяжёлых до фильтра 3 после 0
фильтрующий вес 6

Разбор: где проходит граница

Если лёгкая часть соединяет только вершины 0 и 1, тяжёлое ребро (1,2) отбрасывать нельзя. Связность его концов ещё не доказана. Фильтр смотрит на компоненты после обработки лёгкой части, а не просто на наличие концов среди уже встреченных вершин. В несвязном графе остов содержит меньше n-1 ребра: пытаться обязательно добрать n-1 означает ждать несуществующее соединение между компонентами.

Что ломается без этого

Загрузка всех отсортированных рёбер в список уничтожает выигрыш внешнего сканирования. Union-find на диске без нового анализа превращает дешёвые логические find в дорогие случайные чтения. Фильтрация до обработки лёгкой части неверна, если основана на ещё не установленных связях. А измерение только времени find игнорирует внешнюю сортировку, которая часто и составляет основную стоимость задачи.

Зачем это в работе

Подход подходит для очень плотного графа сравнительно небольшого множества объектов: например, множество кандидатов связи между фиксированными узлами сети. План памяти должен включать служебные массивы union-find, буферы сортировки и поток вывода. Рёбра можно выдавать по мере выбора, не накапливая результат. До запуска проверь реальный размер одной записи вершины: Python-объекты и упакованные массивы имеют разные накладные расходы, хотя асимптотика одинакова.

Теперь сам

В графе шесть вершин и две компоненты связности. Сколько рёбер будет в минимальном остовном лесе? Достаточно ли для полувнешнего режима того, что один блок рёбер влезает в память?