Двудольное соответствие в графе - PullRequest
Новая
       4

Двудольное соответствие в графе

1 голос
/ 29 октября 2011

У меня есть следующий код, который представляет собой реализацию BPM (двустороннее сопоставление, из теории графов) 

#include <iostream>
#include <cstring>
using  namespace std;
#define M 128
#define N 128
bool graph[M][N];
bool seen[N];
int matchL[M],matchR[N];
int n=4;
int m=4;

bool bpm(int u){

    for(int v=0;v<n;v++) if(graph[u][u])
    {
                if (seen[v]) continue;
                seen[v]=true;
                if(matchR[v] <0 || bpm(matchR[v])){
                    matchL[u]=v;
                    matchR[v]=u;
                    return true;
                }
    }

    return false;

}

int main(){

    graph[0][1]=1;
    graph[0][3]=1;
    graph[1][3]=1;
    graph[0][2]=1;
     memset(matchL,-1,sizeof(matchL));
     memset(matchR,-1,sizeof(matchR));
     int cnt=0;
     // memset(seen,0,sizeof(seen));
     for(int i=0;i<m;i++){

        memset(seen,0,sizeof(seen));
          if(bpm(i)) cnt++;

     }
     cout<<cnt<<endl;
    return 0;
}

Определение cnt и назначение этого кода приведены ниже.

Учитывая двудольный граф, представленный в виде матрицы размером m на n, где graph[i][j] равен true, если существует грань от голубя i до отверстия j, вычисляется максимальное количество голубейкоторые могут найти дыру (по одной на голубя) и оптимальное назначение.

  • graph[m][n], matchL[n], matchR[m] и seen[m] являются глобальными массивами.
  • main() инициализирует matchL[] и matchR[] до -1 во всех компонентах.

  • main() выполняет цикл по всем голубям i и в каждой итерации

    • очищает seen[] до 0 во всех компонентах
    • , вызывает bpm(i) и увеличивает maxflow счетчик
    • bpm(i) возвращает true если голубь i может быть назначена лунка

  • cnt содержит количество счастливых голубей.

В моем окse, значение cnt выводится как 0.Этот алгоритм графика работает правильно, или я сделал какую-то ошибку?

1 Ответ

2 голосов
/ 27 ноября 2011

Либо ваша инициализация неисправна, либо это условие в bpm() неисправно: 

       if (graph[u][u])

На диагонали нет элемента graph, который установлен true, поэтому bpm() всегдатерпит неудачу полностью.Также не ясно, зачем вам нужно тестировать диагональ в одиночку.Может быть, это должно быть if (graph[u][v]), или, может быть, что-то еще.

(Ваш отступ оставляет желать лучшего; крайне условно помещать условие if, такое как это, в ту же строку, что и for Циклическое управление. Кстати, инициализация matchL и matchR работает только на машинах с дополнительным дополнением.)

...