شناسایی مرکز گراف

مرکز گراف (graph center)، رأسی است که شعاع را در گراف موجب می‌شود. یا بطور ساده‌تر می‌توان گفت رأسی که بیشترین فاصله‌اش کمینه باشد. مسئله پیدا کردن این رأس در گراف داده شده است. برای مثال نقاط قرمز شکل روبرو مرکز‌های گراف هستند.

این مسئله برای گراف‌های مختلف، الگوریتم‌های مختلفی دارد زیرا هرچه گراف کلی‌تر شود، حل مشکل‌تر و الگوریتم ها پیچیده‌تر می‌شوند. در اینجا راه‌حلی برای گراف‌های بدون وزن و بدون جهت ارائه می‌دهیم. برای حالتی که گراف درخت است اینجا و همچنین برای حالت وزن‌دار می‌توانید به اینجا مراجعه کنید.

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

فرض کنید $V$ تعداد رأس‌ها و $E$ تعداد یال‌ها باشد. چون به ازای هر رأسی یک‌بار $BFS$ می‌زنیم و چون مرتبه اجرایی هر $BFS$ برابر $O(V + E)$ است، پس مرتبه اجرایی الگوریتم از مرتبه $O(V * (V + E))$ است.
توجه کنید که عمل کمینه پیدا کردن نیز از $O(V)$ است، اما چون مرتبه اش کمتر است پس مرتبه کل را زیاد نمی‌کند و همین باقی می‌ماند.

graph_center.cpp

#include <queue>
#include <vector>
 
using namespace std;
const int MAXN = 100 * 1000 + 10;
 
bool mark[MAXN];
vector<int> adj[MAXN];    //  لیست مجاورت رأس‌ها
 
int n;       // تعداد رأس‌ها
 
int bfs(int v) {
    int far = 0;
    queue<int> q;                // صفی که رأس‌ها در آن قرار می‌گیریند
    queue<int> depth;            // صفی که ارتفاع رأس‌های متناظر در صف بالا قرار دارند
 
    mark[v] = 1;
    q.push(v);
    depth.push(0);              // ارتفاع ریشه از خودش صفر است
 
    while(q.size()) {
        v = q.front();
        far = depth.front();
        q.pop();
        depth.pop();
 
        for(unsigned int i = 0; i < adj[v].size(); i++) {
            int u = adj[v][i];
 
            if (mark[u] == 1)
                continue;
 
            mark[u] = 1;
            q.push(u);
            depth.push(far + 1);      // ارتفاع همسایه یک واحد بیشتر از ارتفاع این رأس است
        }
 
    }
 
    return far;
}
 
int find_center()
{
    int dist = 1<<30;              // تقریبا بینهایت برای اینکه در کمینه تاثیری نگذارد و شعاع را نگه می‌دارد
    int v = 0;                     // مرکز گراف را در این متغیر نگه می‌داریم
    for (int i = 0; i < n; i++)
    {
        int tmp = bfs(i);
        if(tmp < dist)
        {
            dist = tmp;
            v = i;
        }
    }
    return v;
}

• سهولت پیدا کردن مسیر
• آنالیز شبکه‌ها

• مرکز گراف - ویکی‌پدیا