图的直径计算算法的正确性

Question

null

我相信这个答案是正确的，但我无法证明。有人能证明它为什么起作用或提供一个反例吗？

Answer 1

假设不在parentmap中意味着是BFS树中的叶子，那么该算法是错误的。

设图有10个顶点和以下无向边：

0 1
0 4
1 2
1 3
2 3
2 6
2 7
3 8
4 5
4 6
5 9
6 7
6 8
7 8
7 9

有效的BFS树之一（根0)是：

0 1
1 2
1 3
2 7
3 8
0 4
4 6
4 5
5 9

pair<vector<int>, set<int>> bfs(int st, const vector<vector<int>>& g) {
    int n = g.size();
    vector<int> d(n, n);
    d[st] = 0;
    queue<int> q;
    q.push(st);
    set<int> parents;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int to : g[v])
            if (d[to] > d[v] + 1) {
                d[to] = d[v] + 1;
                q.push(to);
                parents.insert(v);
            }
    }
    return {d, parents};
}

int get_max_dist(const vector<vector<int>>& g) {
    int res = 0;
    for (int i = 0; i < (int)g.size(); i++) {
        auto cur = bfs(i, g).first;
        for (int x : cur)
            cerr << x << " ";
        cerr << endl;
        res = max(res, *max_element(cur.begin(), cur.end()));
    }
    cerr << endl;
    return res;
}

int get_max_dist_weird(const vector<vector<int>>& g) {
    auto p = bfs(0, g);
    vector<int> cand;
    int n = g.size();
    for (int i = 0; i < n; i++)
        if (!p.second.count(i))
            cand.push_back(i);
    int res = 0;
    for (int i : cand) {
        auto cur = bfs(i, g).first;
        res = max(res, *max_element(cur.begin(), cur.end()));
    }
    return res;
}

vector<vector<int>> rand_graph(int n) {
    vector<vector<int>> g(n);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (rand() & 1) {
                g[i].push_back(j);
                g[j].push_back(i);
            }
    return g;
}

int main() {
    for (int i = 1;; i++) {
        int n = 10;
        auto g = rand_graph(n);
        int correct = get_max_dist(g);
        int got = get_max_dist_weird(g);
        if (correct != got) {
            cerr << correct << " " << got << endl;
            for (int v = 0; v < n; v++)
                for (int j : g[v])
                    if (v < j)
                        cerr << v << " " << j << endl;
        }
        assert (get_max_dist_weird(g) == get_max_dist(g));
        if (i % 1000 == 0)
            cerr << i << endl;
    }
}