在一棵樹中，將任意兩個節點之間最短距離的最大值定義為該樹的直徑。類似地，在一個無向圖中，將任意兩點間最短距離的最大值定義為圖的直徑。
求樹的直徑一般用兩次bfs解決，當然也可以用兩次dfs，這裡以bfs為例進行說明。先在樹上任選一點A作為起點進行bfs，記錄最後被存取的點B，那麼B離A的距離最遠，再以B為起點進行第二次bfs，即可得到直徑。
#include <bits/stdc++.h>
using namespace std;
int n, vis[100005];
vector<int> g[100005];
void bfs(int start, int &last, int &dist) {
last = dist = 0;
queue<pair<int,int>> q;
memset(vis, 0, sizeof(vis));
q.push(make_pair(start, 0)); vis[start] = 1;
while (!q.empty()) {
pair<int,int> pr = q.front(); q.pop();
last = pr.first;
dist = pr.second;
for (auto i : g[pr.first]) {
if (!vis[i]) {
q.push(make_pair(i, pr.second+1));
vis[i] = 1;
}
}
}
}
int main() {
cin >> n;
int x, y, last, dist;
for (int i = 1; i < n; i++) {
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
bfs(x, last, dist);
bfs(last, last, dist);
cout << dist << endl;
return 0;
}
由於圖可能不連通，且可能有環，不能使用類似樹的方法求解，考慮用更為一般的做法，根據直徑定義，先通過floyd演演算法求出任意兩點間的最短距離，再取最大值即可，注意圖不連通的情況。
#include <bits/stdc++.h>
using namespace std;
int n, m, d[105][105];
const int inf = 0x3f3f3f3f;
int main() {
memset(d, 0x3f, sizeof(d));
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
d[x][y] = d[y][x] = 1;
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i+1; j <= n; j++)
ans = max(ans, d[i][j]);
cout << (ans == inf ? -1 : ans) << endl;
return 0;
}