5

グラフの中心点を見つける方法を考えるのに苦労しています。つまり、他のすべてのものへの最大距離を最小化するグラフ上のノードです。

例えば：

3つのノードが一列に並んだグラフがあるとしましょう(のように1-2-3)。

明らかに、このグラフの中心点が であることは簡単にわかります2。しかし、そのようなものを実装するにはどうすればよいでしょうか?

私が知っている唯一のアルゴリズムは、BFS/DFS/Prim と Kruskal のものです。この場合、Prim と Kruskal のアルゴリズムは実際には適用されません。ここで BFS を使用する必要があると思いますか? 唯一の問題は、開始するノードに応じて BFS が異なる順序を返すのではないかということです。

4

2 に答える 2

3

かなり密度の高いグラフの場合:

  1. Floyd-Warshall アルゴリズムを使用してすべての最短パス マトリックスを構築する
  2. 各行の最大値を見つけます - これは対応する頂点 (ノード) の離心率です
  3. 最小の偏心を持つ頂点を選択します - それらは中心ノードです (最小の偏心はグラフの半径です)

複雑さ O(V^3) (小さい定数を使用)

グラフがまばらな場合は、各頂点またはジョンソンのアルゴリズムから BFS を使用できます

(O(V^2+ V*E), O(V^2*logV + V*E))

年度:

0 1 2   //ecc = 2
1 0 1   //ecc = 1 - central point
2 1 0   //ecc = 2

ツリーを使用している場合 (消えたコメントで MST が言及されているため) - より高速な方法があります。

  1. 任意の頂点からの 1 つの BFS
  2. 見つかった最も遠い頂点からの別の BFS
  3. 2 番目の BFS の最長パスで中間の頂点を取得する

O(V + E)

于 2013-03-28T05:55:39.257 に答える