Исправление алгоритма минимального разреза Каргера со структурой данных union-find

Это может помочь сделать резервную копию и подумать о том, почему здесь вообще есть структура union-find и почему стоит улучшить оператор continue.

Концептуально каждое выполненное сокращение изменяет график следующим образом:

1. Сокращенные узлы заменяются одним узлом.
2. Ребра, инцидентные любому узлу, заменяются ребром нового узла соединения.
3. Ребра, идущие между двумя предыдущими узлами, удаляются.

Тогда возникает вопрос, как на самом деле сделать это с графиком. Код, который вы нашли, делает это лениво. На самом деле это не меняет график, когда сокращение выполнено. Вместо этого он использует структуру union-find, чтобы показать, какие узлы теперь эквивалентны друг другу. Когда он выбирает случайное ребро, он затем должен проверить, является ли это ребро одним из тех, которые были бы удалены на шаге (3). Если это так, он пропускает его и движется дальше. Это приводит к тому, что ранние сокращения выполняются очень быстро (вероятность выбора двух ребер, являющихся частью сжатых узлов, очень мала, когда стягивается несколько ребер), но более поздние сокращения могут быть намного медленнее (как только ребра начали сжиматься, ребер могли быть удалены).

Вот простая модификация, которую вы можете использовать, чтобы ускорить этот шаг. Всякий раз, когда вы выбираете ребро для сокращения и обнаруживаете, что его конечные точки уже соединены, отбрасывайте это ребро и удаляйте его из списка ребер, чтобы оно больше никогда не выбиралось. Это можно сделать, поменяв местами это ребро. edge в конец списка ребер, затем удаляя последний элемент списка. Это приводит к тому, что каждое обработанное ребро больше никогда не будет видно, поэтому на всех итерациях алгоритма каждое ребро будет обработано не более одного раза. Это дает время выполнения одной рандомизированной фазы сжатия как O (m + n (n)), где m — количество ребер, а n — количество узлов. Множитель (n) возникает из-за использования структуры union-find.

Если вы действительно хотите удалить все подобия этого оператора continue, альтернативным подходом будет прямое моделирование сжатия. После каждого сжатия перебирайте все m ребер и настраивайте каждое из них, наблюдая, должно ли оно оставаться неизменным, указывать на новый сжатый узел или вообще быть удалено. Это займет время O(m) на сокращение при чистых затратах O(mn) для расчета общего минимального сокращения.

Есть способы ускорить процесс помимо этого. В исходной статье Каргера предлагается генерировать случайную перестановку ребер и использовать бинарный поиск по этому массиву с разумным использованием BFS или DFS, чтобы найти разрез, произведенный за время O (m), что немного быстрее, чем O (m + n ( n)) подход для больших графов. Основная идея заключается в следующем:

1. Исследуйте средний элемент списка ребер.
2. Запустите BFS на графе, сформированном с использованием только этих ребер, и посмотрите, есть ли ровно два связанных компонента.
3. Если так, отлично! Эти два CC - те, которые вам нужны.
4. Если есть только один CC, отбросьте заднюю половину массива ребер и повторите попытку.
5. Если имеется более одного CC, сверните каждый CC в один узел и обновите глобальную таблицу, указав, к какому CC принадлежит каждый узел. Затем отбросьте первую половину массива и повторите попытку.

Стоимость каждого BFS составляет O(m), где m — количество ребер в графе, и это дает повторение T(m) = T(m/2) + O(m), потому что на каждом этапе мы отбрасывая половину краев. Это дает общее время O(m), хотя, как вы можете видеть, это гораздо более сложный способ кодирования этого алгоритма!

Обобщить:

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

2. Чтобы устранить это продолжение, не жертвуя временем выполнения алгоритма, вам нужно сделать серьезную операцию и изменить подходы к чему-то лишь незначительно асимптотически более быстрому, чем сохранение продолжения.

Надеюсь это поможет!