グラフの直径を計算するアルゴリズムの正しさ

Question

私は初級CSコースのTAです。学生に与えられる1つの質問は、重み付けされていない無向グラフの直径を決定するためにBFSを使用する方法でした。学生は効率性を評価されないと言われたので、予想される答えは、あらゆるノードから他のすべてのノードまでBFSを実行し、これらのBFS実行から最大距離を返したブルートフォースアルゴリズムでした。生徒には、擬似コードで参照できるBFSメソッドが用意されていました。擬似コードは入力としてノードを取得し、グラフの各ノードから開始ノードまでの距離（distmap）と各ノードからの距離入力ノード（parentmap）からの最短パスに沿って、その「親ノード」に移動します。

1. グラフから任意のノードを選択し、それからBFSを実行します。

   一人の学生は、次のアルゴリズムを書きました。

   1. 実行BFS：
   2. はparentmapの値（BFS木のすなわち葉）
   3. 初期化MAX_DIST各ノードについてN温度で
   4. 0ではないすべてのノードの設定温度を作成しますdistmapの各値DのN
   5. から：D> MAX_DIST THEN DにMAX_DIST等しく設定した場合
2. RETURNのMAX_DIST

私はこの答えが正しいと信じているが、私はそれを証明することができません。誰かがそれが動作する理由を証明したり、反例を提供することはできますか？

Answer 1

親マップにないということは、BFSツリーのリーフであることを意味していると仮定すると、アルゴリズムは間違っています。

グラフ10個の頂点と次の無向エッジを持ってみましょう：（ルート0で）有効BFS木の

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 

一つは：

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

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

確かに、アルゴリズムは、このように正しいことを証明することはできませんが、それは非常にですそれがそうでない場合、反例を見つける可能性が高い。

Answer 2

たぶん少しシンプルなカウンター例：

あなたが赤からあなたのBFSを開始する場合には、このグラフの最大距離はグリーンのノード（4）との間にあることは明らかですが、 Tempは、2つの青いノードのみで構成され、3の不正確な「直径」を与えます。