فاصله بین دو رأس را طول کوتاه‌ترین مسیر ممکن بین آن دو تعریف می‌کنیم. حال به ازای هر رأسی اگر اسم بیشترین فاصله آن تا سایر رأس‌ها را خروج از مرکز آن رأس بگیریم، قطر گراف برابر بیشترین خروج از مرکز است.
توجه کنید که قطر همیشه برابر طولانی‌ترین مسیر نیست، برای مثال در گراف متشکل از یک دور، طولانی‌ترین مسیر برابر $n-1$ است، ولی قطر $n/2$ است.

این مسئله در حالت کلی کمی سخت است و حل‌های گوناگونی برای آن وجود دارد، بدین منظور این مسئله را به چند حالت تقسیم می‌کنیم و تنها بخش اول را در اینجا شرح می‌دهیم.

1. گراف‌های بدون‌جهت و بی‌وزن که در این بخش بررسی می‌شوند و با $n$ بار جست‌و‌جوی سطح‌اول قابل حل است.
2. درخت‌ها، که راه‌حلی از مرتبه‌زمانی $O(n+e)$ دارد. به بخش درخت‌ها مراجعه کنید.
3. گراف‌های وزن‌دار که راه‌حل‌های مختلفی از جمله $O(n³)$ دارد. برای اطلاعات بیشتر به الگوریتم فلوید-وارشال و الگوریتم دایکسترا را ببینید.

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

چون در روش گفته شده، به ازای هر رأسی یک پیمایش انجام می‌دهیم پس زمان اجرا از $O(n * (n + e))$ است. سپس بین $n$ مقدار ممکن ماکسیمم می‌گیریم که در $O(n)$ قابل محاسبه است، پس زمان اجرا برابر $O(n * (n + e))$ است.
از آن‌جا که به ازای هر رأسی تنها یک عدد نگه می‌داریم پس مرتبه حافظه از مرتبه پیمایش است.

فرض می‌کنیم گراف را به صورت لیست مجاورت به ما داده‌اند.

A.c

#include <queue>
#include <vector>
 
const int MAXN = 100 * 1000 + 10;
 
bool mark[MAXN];
int vector<int> adj[MAXN];
 
void bfs(int v) {
    int far = 0;
    queue<int> q;
    queue<int> depth;
 
    mark[v] = 1;
    q.push(v);
    depth_v.push(0);
 
    while(q.size()) {
        v = q.front();
        far = depth.front();
        q.pop();
        depth.pop()
 
        for(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_diameter()
{
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(bfs(i), ans);
    return ans;
}

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

پیدا کردن سقف شعاع

• PsudoDiameter
• فاصله در گراف - ویکی‌پدیا