الگوریتم تطابق بیشینه در گراف دوبخشی

الگوریتم زیر با گرفتن ماتریس مجاورت، یالهای تطابق بیشینه را به دست میدهد .

روش کار الگوریتم بدین صورت است که برای هر رأس در صورتی تا به حال برایش جفتی پیدا نشده باشد یک مسیر M-افزوده از آن رأس پیدا می‌کند، سپس با تعویض یالهای مسیر افزوده اندازه گراف را افزایش میدهد .

ورودی و خروجی

e ماتریس مجاورت گراف دوبخشی است. N تعداد رأسهای بخش اول گراف و M تعداد راسهای بخش دوم گراف است.

بعد از پایان الگوریتم آرگومان [match[i جفت رأس i در بخش اول را بدست می‌دهد.

لازم به ذکر است که برنامه زیر تحت استاندارد زبان برنامه نویسی ++C نوشته شده‌است.

الگوریتم

bool find (int node) {
    if (mark[node])
        return false;
    mark[node] = true;
    for (int i = 1; i <= m; i++) {
        if (e[node][i] && match2[i] == 0) {
            match2[i] = node;
            match[node] = i;
            mark[node] = false;
            return true;
        }
    }
    for (int i=1; i<=m; i++) {
        if (e[node][i] && find(match2[i])) {
            match[node] = i;
            match2[i] = node;
            mark[node] = false;
            return true;
        }
    }
    mark[node] = false;
    return false;
}

void matching() {
    for (int i = 1; i <= n; i++)
    if (match[i] == 0)
        find(i);
}

منابع

• کتاب آشنایی با نظریه گراف اثر دوگلاس بی.وست