Рубрики

Алгоритм Хопкрофта – Карпа для максимального соответствия | Набор 2 (реализация)

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

Алгоритм Хопкрофта – Карпа для максимального соответствия | Комплект 1 (Введение)

Есть несколько важных вещей, которые нужно отметить, прежде чем мы начнем реализацию.

  1. Нам нужно найти путь расширения (путь, который чередуется между совпадающими и не совпадающими ребрами и имеет свободные вершины в качестве начальной и конечной точек).
  2. Как только мы найдем альтернативный путь, нам нужно добавить найденный путь к существующему сопоставлению . Здесь добавление пути означает создание предыдущих совпадающих ребер на этом пути как несоответствующих, а предыдущие несоответствующие ребра как совпадающих.

Идея состоит в том, чтобы использовать BFS (поиск в ширину), чтобы найти пути расширения. Поскольку BFS проходит уровень за уровнем, он используется для разделения графа на слои совпадающих и не совпадающих ребер. Добавлена фиктивная вершина NIL, которая соединена со всеми вершинами с левой стороны и со всеми вершинами с правой стороны. Следующие массивы используются для поиска пути расширения. Расстояние до NIL инициализируется как INF (бесконечно). Если мы начинаем с фиктивной вершины и возвращаемся к ней, используя чередующиеся пути различных вершин, то существует расширяющий путь.

  1. pairU []: массив размером m + 1, где m — количество вершин в левой части двудольного графа. pairU [u] сохраняет пару u на правой стороне, если u соответствует, и NIL в противном случае.
  2. pairV []: массив размером n + 1, где n — количество вершин в правой части двудольного графа. pairV [v] сохраняет пару v на левой стороне, если v соответствует, и NIL в противном случае.
  3. dist []: массив размером m + 1, где m — число вершин в левой части двудольного графа. dist [u] инициализируется как 0, если u не совпадает, и INF (бесконечно) в противном случае. dist [] of NIL также инициализируется как INF

Когда найден путь расширения, DFS (Поиск в глубину) используется для добавления путей к текущему сопоставлению. DFS просто следует настройке массива расстояний с помощью BFS. Он заполняет значения в pairU [u] и pairV [v], если v находится рядом с u в BFS.

Ниже приведена реализация вышеописанного алгоритма Хопкрофта Карпа на С ++.

// C ++ реализация алгоритма Хопкрофта Карпа для
// максимальное совпадение
#include<bits/stdc++.h>

using namespace std;

#define NIL 0
#define INF INT_MAX

  
// Класс для представления двудольного графа для Хопкрофта
// Карп реализации

class BipGraph

{

    // m и n - количество вершин слева

    // и правые стороны двудольного графа

    int m, n;

  

    // adj [u] сохраняет примыкания левой стороны

    // вершина 'u'. Значение u колеблется от 1 до m.

    // 0 используется для фиктивной вершины

    list<int> *adj;

  

    // Это в основном указатели на необходимые массивы

    // для hopcroftKarp ()

    int *pairU, *pairV, *dist;

  

public:

    BipGraph(int m, int n); // Конструктор

    void addEdge(int u, int v); // Добавить ребро

  

    // Возвращает true, если есть путь расширения

    bool bfs();

  

    // Добавляем увеличивающий путь, если есть одно начало

    // с тобой

    bool dfs(int u);

  

    // Возвращает размер максимального соответствия

    int hopcroftKarp();

};

  
// Возвращает размер максимального соответствия

int BipGraph::hopcroftKarp()

{

    // pairU [u] сохраняет пару u в совпадении, где u

    // это вершина в левой части двудольного графа.

    // Если у вас нет пары, то pairU [u] равен NIL

    pairU = new int[m+1];

  

    // pairV [v] сохраняет пару v в соответствии. Если v

    // пары нет, то pairU [v] равно NIL

    pairV = new int[n+1];

  

    // dist [u] сохраняет расстояние до левых боковых вершин

    // dist [u] на единицу больше, чем dist [u '], если u следующий

    // к увеличивающемуся пути

    dist = new int[m+1];

  

    // Инициализируем NIL как пару всех вершин

    for (int u=0; u<m; u++)

        pairU[u] = NIL;

    for (int v=0; v<n; v++)

        pairV[v] = NIL;

  

    // Инициализировать результат

    int result = 0;

  

    // Продолжаем обновлять результат, пока есть

    // увеличивающий путь.

    while (bfs())

    {

        // Найти свободную вершину

        for (int u=1; u<=m; u++)

  

            // Если текущая вершина свободна и есть

            // увеличивающий путь от текущей вершины

            if (pairU[u]==NIL && dfs(u))

                result++;

    }

    return result;

}

  
// Возвращает true, если есть путь расширения, иначе возвращает
// ложный

bool BipGraph::bfs()

{

    queue<int> Q; // целочисленная очередь

  

    // Первый слой вершин (установите расстояние равным 0)

    for (int u=1; u<=m; u++)

    {

        // Если это свободная вершина, добавить ее в очередь

        if (pairU[u]==NIL)

        {

            // вы не соответствует

            dist[u] = 0;

            Q.push(u);

        }

  

        // Иначе устанавливаем расстояние как бесконечное, чтобы эта вершина

        // рассматривается в следующий раз

        else dist[u] = INF;

    }

  

    // Инициализируем расстояние до NIL как бесконечное

    dist[NIL] = INF;

  

    // Q будет содержать вершины только левой стороны.

    while (!Q.empty())

    {

        // Удаление вершины из очереди

        int u = Q.front();

        Q.pop();

  

        // Если этот узел не NIL и может предоставить более короткий путь к NIL

        if (dist[u] < dist[NIL])

        {

            // Получаем все смежные вершины убранной вершины u

            list<int>::iterator i;

            for (i=adj[u].begin(); i!=adj[u].end(); ++i)

            {

                int v = *i;

  

                // Если пара v не рассматривается до сих пор

                // (v, pairV [V]) еще не исследовано ребро.

                if (dist[pairV[v]] == INF)

                {

                    // Рассмотрим пару и добавим ее в очередь

                    dist[pairV[v]] = dist[u] + 1;

                    Q.push(pairV[v]);

                }

            }

        }

    }

  

    // Если бы мы могли вернуться к NIL, используя альтернативный путь

    // вершины, то есть путь расширения

    return (dist[NIL] != INF);

}

  
// Возвращает true, если существует путь расширения, начинающийся со свободной вершины u

bool BipGraph::dfs(int u)

{

    if (u != NIL)

    {

        list<int>::iterator i;

        for (i=adj[u].begin(); i!=adj[u].end(); ++i)

        {

            // рядом с тобой

            int v = *i;

  

            // Следуйте расстояниям, установленным BFS

            if (dist[pairV[v]] == dist[u]+1)

            {

                // Если dfs для пары v также возвращает

                // правда

                if (dfs(pairV[v]) == true)

                {

                    pairV[v] = u;

                    pairU[u] = v;

                    return true;

                }

            }

        }

  

        // Если нет пути расширения, начинающегося с u.

        dist[u] = INF;

        return false;

    }

    return true;

}

  
// Конструктор

BipGraph::BipGraph(int m, int n)

{

    this->m = m;

    this->n = n;

    adj = new list<int>[m+1];

}

  
// Добавить ребро от u к v и v к u

void BipGraph::addEdge(int u, int v)

{

    adj[u].push_back(v); // Добавить вас в список v.

}

  
// Программа для водителя

int main()

{

    BipGraph g(4, 4);

    g.addEdge(1, 2);

    g.addEdge(1, 3);

    g.addEdge(2, 1);

    g.addEdge(3, 2);

    g.addEdge(4, 2);

    g.addEdge(4, 4);

  

    cout << "Size of maximum matching is " << g.hopcroftKarp();

  

    return 0;

}

Выход:

Size of maximum matching is 4

Вышеуказанная реализация в основном принята из алгоритма, представленного на вики-странице алгоритма Хопкрофта Карпа .

Эта статья предоставлена Рахул Гупта . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Алгоритм Хопкрофта – Карпа для максимального соответствия | Набор 2 (реализация)

0.00 (0%) 0 votes