الگوریتم استور- واگنر

الگوریتم استور-واگنر یک الگوریتم بازگشتی برای حل مسئله برش کمینه در گراف‌های وزن‌دار بدون جهت با وزن‌های نامنفی است. این الگوریتم در سال ۱۹۹۵ توسط مکتیلد استور و فرانک واگنر پیشنهاد داده شد. همبندی گراف یکی از موضوعات کلاسیک در نظریه گراف‌ها می‌باشد و استفاده‌های کاربردی بسیاری مانند طراحی تراشه و مدار، قابل اعتماد بودن شبکات ارتباطی، برنامه‌ریزی حمل و نقل و خوشه بندی دارد. پیدا کردن برش کمینه یک گراف وزن‌دار یه مسئله اساسی الگوریتمی است. به‌طور دقیق این کار شامل پیدا کردن دو بخش مجزا از گراف بطوری که جمع وزن یال‌هایی که این دو بخش را به هم متصل می‌کنند کمینه شود می‌باشد.
برش کمینه در یک گراف از موضوعات بسیار مهم در زمینه بهینه‌سازی شبکه است. برش، برداشتن شماری از یال‌های یک گراف همبند است، به گونه‌ای که گراف را به دو بخش ناهمبند تبدیل کند. حال اگر وزن هر یال هزینه برداشتن آن یال در نظر گرفته شود، برش کمینه برشی است که جمع هزینه ایجاد آن کمینه شود.

زمان اجرا

زمان اجرای الگوریتم برش کمینه، در واقع زمان اجرای  بار MinimumCutPhase است. زمان اجرای MinimumCutPhase حداکثر از  است. در نتیجه زمان اجرای کل الگوریتم از  بدست می‌آید. 
انتخاب کردن رأس بعدی که باید به مجموعه  اضافه شود می‌تواند در زمان اجرای الگوریتم تأثیر زیادی داشته باشد. برای بهینه کردن الگوریتم و آسان شدن پیدا کردن رأس مورد نظر در هر مرحله، در طول اجرای هر فاز همه راس‌هایی که در مجموعه نیستند، درون یک صف اولویت درج می‌شوند. کلید هر راس از  مجموع وزن همه یال‌هایی است که آن راس را به مجموعه  متصل می‌کنند. هر بار که یک راس  به  اضافه می‌شود باید صف اولویت به‌روزرسانی شود. در به‌روزرسانی، راس  را از صف حذف می‌کنیم و برای همه راس‌هایی که در  نیستند کلید را به اندازه وزن یال بین آن راس و  در صورت وجود چنین یالی، زیاد می‌کنیم. این عمل هر بار با زمان سرشکن ،  بار اجرا می‌شود. از طرفی پیدا کردن کلید بیشینه به کمک هیپ فیبوناتچی با زمان سرشکن ،  بار تکرار می‌شود. پس زمان اجرای مرحله پیدا کردن رأس مناسب برای اضافه کردن به  حداکثر از  است.

کد الگوریتم

// Adjacency matrix implementation of Stoer–Wagner min cut algorithm.//// Running time://     O(|V|^3)//// INPUT: //     - graph, constructed using AddEdge()//// OUTPUT://     - (min cut value, nodes in half of min cut)#include <cmath>#include <vector>#include <iostream>using namespace std;typedef vector<int> VI;typedef vector<VI> VVI;const int INF = 1000000000;pair<int, VI> GetMinCut(VVI &weights) 
{
    int N = weights.size();
    VI used(N), cut, best_cut;
    int best_weight = -1;

    for (int phase = N-1; phase>= 0; phase--) 
    {
        VI w = weights[0];
        VI added = used;
        int prev, last = 0;
        for (int i = 0; i <phase; i++) 
        {
            prev = last;
            last = -1;
            for (int j = 1; j <N; j++)
            {
                if (!added[j] && (last == -1 || w[j]> w[last])) last = j;
            }
            if (i == phase-1) 
            {
                for (int j = 0; j <N; j++) weights[prev][j] += weights[last][j];
                for (int j = 0; j <N; j++) weights[j][prev] = weights[prev][j];
                used[last] = true;
                cut.push_back(last);
                if (best_weight == -1 || w[last] <best_weight) 
                {
                    best_cut = cut;
                    best_weight = w[last];
                }
            }
            else 
            {
                for (int j = 0; j <N; j++)
                {
                    w[j] += weights[last][j];
                    added[last] = true;
                }
            }
        }
    }
    return make_pair(best_weight, best_cut);}
const int maxn = 550;  
const int inf = 1000000000;  
int n, r;  
int edge[maxn][maxn], dist[maxn];  
bool vis[maxn], bin[maxn];  
void init()  
{  
    memset(edge, 0, sizeof(edge));  
    memset(bin, false, sizeof(bin));  
}  
int contract( int &s, int &t )          // Find s,t  {  
    memset(dist, 0, sizeof(dist));  
    memset(vis, false, sizeof(vis));  
    int i, j, k, mincut, maxc;  
    for(i = 1; i <= n; i++)  
    {  
        k = -1; maxc = -1;  
        for(j = 1; j <= n; j++)if(!bin[j] && !vis[j] && dist[j]> maxc)  
        {  
            k = j;  maxc = dist[j];  
        }  
        if(k == -1)return mincut;  
        s = t;  t = k;  
        mincut = maxc;  
        vis[k] = true;  
        for(j = 1; j <= n; j++)if(!bin[j] && !vis[j])  
            dist[j] += edge[k][j];  
    }  
    return mincut;  
}int Stoer_Wagner()  
{  
    int mincut, i, j, s, t, ans;  
    for(mincut = inf, i = 1; i <n; i++)  
    {  
        ans = contract( s, t );  
        bin[t] = true;  
        if(mincut> ans)mincut = ans;  
        if(mincut == 0)return 0;  
        for(j = 1; j <= n; j++)if(!bin[j])  
            edge[s][j] = (edge[j][s] += edge[j][t]);  
    }  
    return mincut;  
}