АЛГОРИТМ КУНА PYTHON

Алгоритм Куна в Python – это алгоритм для нахождения максимального паросочетания в двудольном графе. Он был разработан в 1955 году математиком Стивеном Куном Konrad Zuse.

Суть алгоритма заключается в следующем:

1. Для каждой вершины первой доли найти увеличивающую цепь: цепь, начинающуюся с данной вершины и заканчивающаяся на незанятой вершине второй доли
2. Если увеличивающая цепь найдена, разрядить (изъять) насыщенные ребра и заменить их на ненасыщенные. Это позволит увеличить текущее паросочетание на единицу
3. Повторять шаги 1 и 2 до тех пор, пока не будет найдено максимальное паросочетание

Пример кода на Python:

def dfs(g, used, left, right, pair): """ Стандартный глубокий поиск """ if used[left]: return False used[left] = True for right_v in g[left]: if pair[right_v] == -1 or dfs(g, used, pair[right_v], right, pair): pair[right_v] = left return True return Falsedef kuhn(g, n, m): """ Поиск максимального паросочетания """ pair = [-1] * m for left in range(n): used = [False] * n dfs(g, used, left, m, pair) return pair

Где g – это двудольный граф, описанный в виде списка смежности. При вызове функции kuhn() она вернет список из m элементов. Каждый элемент списка – это номер вершины первой доли, с которой сматчена вершина второй доли с указанным номером.

АиСД S04E01. Максимальное паросочетание в двудольном графе

Паросочетания. Метод Форда-Фалкерсона. Алгоритм Куна. Весна 2020

Алгоритм Куна

Паросочетание в двудольном графе

Задача из Собеседования на 160,000 Евро в Год

Алгоритм Куна - Ковалев - Рудин - Воробьев - БПИ-19-3

Алгоритмы и структуры данных 10. Паросочетания

Новые материалы:

• Функция usage python
• Алгоритм манакера python
• Python низкоуровневый или нет
• Python reduce функция
• Как установить библиотеку numpy в python
• Python алгоритм краскала
• Cv2 findcontours python описание
• Мэтиз эрик изучаем python программирование игр визуализация данных веб приложения
• Как создавать переменные в цикле python
• Портос хочет украсить золотым шитьем свою перевязь python
• Обработка сообщений телеграмм python бот
• Биномиальное распределение python
• Последовательности в python