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

Question

我是 CS 入门课程的助教，给学生的一个问题是如何使用 BFS 来确定未加权的无向图的直径。学生们被告知他们不会根据效率进行评分，因此预期的答案是一个蛮力算法，他们运行从每个节点到每个其他节点的 BFS，并返回这些 BFS 运行的最大距离。向学生提供了一种 BFS 方法，他们可以在他们的伪代码中引用该方法，该方法将一个节点作为输入并返回两个映射：一个是从图中的每个节点到它到起始节点的距离（称为 distmap），另一个是每个节点到它的 'parent node' 沿着从输入节点（称为 parentmap）的最短路径。

一位同学写了如下算法：

Choose an arbitrary node from the graph and run BFS from it.

Create a set Temp of all the nodes that are not values in parentmap (i.e. the leaves of the BFS tree)

Initialize max_dist to 0

For each node n in Temp:

Run BFS from n

For each value d in distmap:

IF d > max_dist THEN set max_dist equal to d

RETURN max_dist

我相信这个答案是正确的，但我无法证明。有人可以证明它为什么有效或提供反例吗？

Answer 1

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

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

其中一个有效的 BFS 树（根 0）是：

叶子是6, 7, 8, 9，所以这个解returns 3. 那是错误的。答案是4（就是3和5之间的距离）。

获取所有最远的节点对于此测试也不起作用。

您可以生成数百万个小的随机测试用例并检查解决方案是否产生正确答案，而不是要求某人找到反例。这是我用来生成这个案例的代码（它看起来不太好，但它完成了工作）：

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

当然，你不能用这种方式证明算法是正确的，但如果不是这样，很有可能找到一个反例。

Answer 2

也许是一个稍微简单的反例：

很明显，该图中的最大距离在绿色节点 (4) 之间，但是如果您从红色节点开始 BFS，Temp 将仅包含两个蓝色节点，这给出了不正确的 "diameter" of 3.

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

Correctness of algorithm for computing diameter of a graph

algorithm

graph-theory

graph-algorithm

breadth-first-search