Алгоритмы и структуры данных

Нахождение максимального паросочетания в двудольном графе

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

Алгоритм:
1. Разделите вершины графа на две доли.
2. Инициализируйте пустое множество паросочетания.
3. Пока есть непомеченные вершины:
- Выберите непомеченную вершину из первой доли и запустите поиск в глубину (DFS) из этой вершины.
- В процессе DFS для каждой непомеченной вершины во второй доле:
* Если вершина не принадлежит паросочетанию, добавьте ребро между текущей вершиной и найденной вершиной в паросочетание.
* Если вершина принадлежит паросочетанию, найдите альтернативную цепь с помощью попеременного обхода паросочетания и пометьте все вершины этой цепи.
4. Верните множество паросочетания.

Сложность: O(V * E)

www.tgoop.com/the_algorithms/4630

6.0K viewsDec 7, 2023 at 11:02

Нахождение максимального паросочетания в двудольном графе

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

Алгоритм:
1. Разделите вершины графа на две доли.
2. Инициализируйте пустое множество паросочетания.
3. Пока есть непомеченные вершины:
- Выберите непомеченную вершину из первой доли и запустите поиск в глубину (DFS) из этой вершины.
- В процессе DFS для каждой непомеченной вершины во второй доле:
* Если вершина не принадлежит паросочетанию, добавьте ребро между текущей вершиной и найденной вершиной в паросочетание.
* Если вершина принадлежит паросочетанию, найдите альтернативную цепь с помощью попеременного обхода паросочетания и пометьте все вершины этой цепи.
4. Верните множество паросочетания.

Сложность: O(V * E)

BY Алгоритмы и структуры данных