#6. Алгоритм Краскала (Kruskal's algorithm) | Алгоритмы на Python

Рассматривается известный алгоритм Краскала для поиска минимального остова взвешенного неориентированного графа. Приведена реализация на языке Python.
algorithm-kruskal.py: github.com/selfedu-rus/python...

[@user-nh6pt5rt8g]

Очень крутое видео, помогло разобраться.
Правда алгоритм я немного переделал, если кому-то нужно, чтобы данный алгоритм работал на графах с большим количеством подгрупп, вот часть кода, которую можно заменить:
for edge in edges:
if edge[1] not in isolated[edge[0]]:
min_span.append(edge)
connector = isolated[edge[1]].copy()
isolated[edge[0]] += isolated[edge[1]]
change_isolated_parts(isolated, connector, isolated[edge[0]])
min_span_graph = nx.Graph()
min_span_graph.add_edges_from(min_span)
return min_span_graph
def change_isolated_parts(isolated: dict, connector: list, replacer: list) -> None:
for key, value in isolated.items():
if value == connector:
isolated[key] = replacer
Я тестировал на графах размером 150 вершин, всё работает хорошо.
Знаю, что код можно улучшить, используя правильный подход к работе с памятью, но сам уже не стал заморачиваться.

[@dahtes2107]

Вот уже как неделю начал читать и изучать книгу "Разработка и приминение алгоритмом" Клейнберга, только подумал, что читать это разбирать на бумаге это хорошо, не плохо было бы еще видео посмотреть, как говорят ассоциативную память подключить, как тут захожу к тебе на канал и тут Годнота, прямо подарок под ёлочку)) Спасибо тебе за труды

[@e_butcher]

Здравствуйте.
Давно хотел реализовать при помощи графа алгоритм оптимизации долгов. Пример: человек А должен человеку В 100 рублей, а человек В должен человеку С 120 рублей. После оптимизации человек А должен человеку С 100 рублей, а В должен С 20. С помощью каких методов это можно было бы сделать? Мне казалось, что можно использовать ориентированные взвешенные графы, но дальше этого пока не продвинулся. Буду рад помощи!

[@0ver4ance]

Почему на первой итерации алгоритма мы можем объединять вершины только в том случае, если хотя бы одна из вершин является еще не объединенной с другой? Везде где я читал про этот алгоритм этого ограничения нет. Единственное ограничение - это то, чтобы вершины на концах очередного ребра находились в разных множествах. Если честно, то в этом курсе не раз встречаю какие-то выдуманные условия. Много Ваших курсов прошел и они замечательные. Вы очень много хорошего делаете в плане преподавания. Но такое ощущение, как будто бы не вы этот курс делали

[@user-gd4ik4ds3g]

Стоит заметить, что приведенный код можно оптимизировать, не применяя иные структуры данных.
Следующую конструкцию, которая требует перебора множества для выявления совпадения:
if r[1] not in U or r[2] not in U:
if r[1] not in U and r[2] not in U:
можно заменить на:
if D.get(r[1]) is None or D.get(r[2]) is None:
if D.get(r[1]) is None and D.get(r[2]) is None:
Тогда проверка вершины будет выполняться за O(1), так как мы работаем с хэширванием. В таком исполнении множество U становится излишним.
P.S. Всем хорошего кода!

[@user-vs1ix8py6g]

Доброго Вам времени суток, уважаемый @selfedu ! Я не могу понять почему проверка создания цикла корректна. Например если мы последовательно добавим ребьра 1-2 3-4 и 2-3, т.к. на последнем шаге и вершина 2, и вершина 3 будут уже в словаре U, алгоритм обнаружит цикл, хотя его тут нет. Был бы благодарен, если бы кто-нибудь прояснил мне этот момент.

[@amogus_bebra_228]

далбаеб там же снизу идет объединение этих разрозненных груп))

[@user-vs1ix8py6g]

@@amogus_bebra_228 Ой, и вправду. Сердечно Вас благодарю!

[@evgenyrudakov6963]

Добрый день! Подскажите пожалуйста, зачем используем переменную gr1 ?

[@selfedu_rus]

Нам нужно по ключу D[r[2]] добавить только одну вершину, мы сохраняем ссылку на нее в переменной gr1, а затем, добавляем в D[r[2]].

[@chariot3870]

@@selfedu_rus но в Python списки изменяемые. Разве мы не должны положить в gr_1 копию списка из D[r[1]], а не ссылку на него? Иначе выйдет так, что мы в D[r[2]] прибавляем уже расширенный список D[r[1]]...

[@selfedu_rus]

@@chariot3870 r[1], r[2], ... - это просто числа - номера вершин

[@amogus_bebra_228]

7:15 то что ты создаешь на 34 строке временную переменную тебе не поможет т.к. ты в неее копируешь ссылку на список а не сам список, поэтому на 36 строке ты добавишь уже конкатенированный список во вторую группу из-за чего там возникают дубликаты. нужно на 34 строчке использовать слайс gr1 = D[r[1]][:]

[@Arteefall]

А какая сложность алгоритма, который вы осуществляете?

[@user-vf7xz3kd9h]

Сам узнать хочу но вроде с заднем случае н в степени 3

[@freesx1306]

@@user-vf7xz3kd9h два цикла O(n+n), но поскольку была сортировка вначале, то O(n*logn)

[@user-vf7xz3kd9h]

@@freesx1306 спосибо но я уже понел

[@0ver4ance]

Я смог придумать только такой самый худший случай, где без учета сортировки получается V/2 * logV. А так как граф связный, то E точно не меньше чем V, а следовательно сортировка ребер перебьет сложность самого алгоритма и получится ElogE. Но в википедии пишут про то, что без учета сортировки оценка E

[@fghinty7623]

перезалив. а почему?

[@selfedu_rus]

Ошибка была, переписал )

[@sanyarud5676]

@@selfedu_rus ну ты даешь)

[@fghinty7623]

@@selfedu_rus ага, посмотрев, понял)

[@luckytima2315]

@@selfedu_rus даже лучший ошибаются :) Вы молодец )

[@ak2ree865]

А как алгоритм выявляет самые короткие ребра не видел в коде сравнения? спасибо!

[@the_sugar5695]

Они не нужны, так как в самом начале происходит сортировка ребер по возрастанию

[@ilyaburov00]

sorted