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

我是介绍性CS课程的助教，给学生的一个问题是如何使用BFS来确定未加权的无向图的直径。学生被告知他们不会被分级以提高效率，所以预期的答案是一个强力算法，他们从每个节点到每个其他节点运行BFS，并从这些BFS运行返回最大距离。给学生们提供了他们可以参考的BFS方法，他们的伪代码输入了一个节点并返回了两个映射：一个从图中的每个节点到它离开始节点的距离（称为distmap），一个来自每个节点到沿着输入节点的最短路径（称为父图）的“父节点”。计算图的直径的算法的正确性

一个学生写了如下算法：

选择从图中的任意节点，并运行它BFS。

创建所有不在parentmap值（BFS树即叶）

初始化max_dist 0

对于每个节点n温度节点的一组温度：

运行BFS从n个

对于distmap每个值d：

IF d> max_dist THEN设定max_dist等于d

RETURN max_dist

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

来源

2017-06-02 Zach B

问题中的图是有向的还是无向的，它是加权的还是未加权的，它是树吗？ –

@JaysonBoubin它是无向的，不加权的，并不一定是一棵树，尽管它可以是 –

不在任何**最短路径上的节点之间存在巨大差异（步骤2的括号中指出了这一点），以及不在**一个**最短路径上的节点（步骤2实际上似乎执行的步骤）。什么是无向图中的“父节点”？ – Dukeling

假设不在父图中意味着在BFS树中是叶，算法是错误的。

让图形具有10个顶点和下面的无向边：

一个有效的BFS树（用root 0）的是：

叶子是6, 7, 8, 9，所以这解决方案返回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; 
    } 
}

当然，你不能证明该算法是正确的这种方式，但它是非常如果不是，可能会找到一个反例。

来源

2017-06-02 18:59:33 kraskevich

谢谢！这正是我正在寻找的。 –

也许稍微简单的反例：

很显然，在这个图中的最大距离是绿色节点（4）之间，但如果你从红色开始您的BFS节点Temp将仅包含两个蓝色节点，它给出了不正确的“直径”3.

来源

2017-06-02 20:53:57

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

回答

相关问题