In a tree, the maximum distance between any two nodes is defined as the diameter of the tree. Similarly, in an undirected graph, the maximum distance between any two points is defined as the diameter of the graph.

The diameter of the tree

The diameter of the tree is usually solved with two BFS, of course, you can also use two DFS, here BFS as an example to illustrate. First, choose any point A on the tree as the starting point for BFS, record the last point B to be accessed, then the distance between B and A is the furthest, and then take B as the starting point for the second BFS to get the diameter.

#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(a); q.pop(a); 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(a) {
    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;
}
Copy the code

Diameter of an undirected graph

Since the graph may be disconnected and may have rings, it cannot be solved by the tree-like method. A more general approach is considered. According to the diameter definition, the shortest distance between any two points can be calculated by Floyd algorithm first, and then the maximum value can be taken.

#include <bits/stdc++.h>
using namespace std;
int n, m, d[105] [105];
const int inf = 0x3f3f3f3f;
int main(a) {
    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;
}
Copy the code

Resource portal

• Pay attention to [== do a gentle program ape ==] public account
• In [== do a tender program ape ==] public account background reply [Python information] [2020 autumn recruit] can get the corresponding surprise oh!

“❤️ thank you.”

• Click “like” to support it, so that more people can see this content.
• Share your thoughts with me in the comments section, and record your thought process in the comments section.