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

===== صورت مسئله =====
مرکز گراف (graph center)، رأسی است که شعاع را در گراف موجب می‌شود. یا بطور ساده‌تر می‌توان گفت رأسی که بیشترین فاصله‌اش کمینه باشد. مسئله پیدا کردن این رأس در گراف داده شده است. 
برای مثال نقاط قرمز شکل روبرو مرکز‌های گراف هستند.{{:آموزش:الگوریتم:220px-graphcenter.svg.png?200 |}}

===== توضیحات =====
این مسئله برای گراف‌های مختلف، الگوریتم‌های مختلفی دارد زیرا هرچه گراف کلی‌تر شود، حل مشکل‌تر و الگوریتم ها پیچیده‌تر می‌شوند. در اینجا راه‌حلی برای گراف‌های بدون وزن و بدون جهت ارائه می‌دهیم. برای حالتی که گراف درخت است [[آموزش:الگوریتم:محاسبه‌ی_قطر_و_مرکز_درخت|اینجا]] و همچنین برای حالت وزن‌دار می‌توانید به [[آموزش:الگوریتم:لگوریتم_فلوید-وارشال|اینجا]] مراجعه کنید.

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

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

===== پیاده‌سازی اولیه =====

<code cpp 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;
}



</code>


===== کابردها =====
  * [[https://en.wikipedia.org/wiki/Facility_location_problem|سهولت پیدا کردن مسیر]]
  * [[https://en.wikipedia.org/wiki/Centrality#Closeness_centrality|آنالیز شبکه‌ها]]




===== مسائل نمونه =====

===== مراجع =====

  * [[https://en.wikipedia.org/wiki/Graph_center|مرکز گراف - ویکی‌پدیا]]