BFS実装による最大距離は？

Question

私はあなたがBFSを2回使用してundirected unweightedグラフの直径または最大距離を見つけることができることを知っています。私の質問はこのアルゴリズムの詳細です。

これを実装すると、文字通りBFSを2回実行するだけで、最大距離が返されますか？または、各ノードの距離と重量の値をBFSアルゴリズム全体に設定し、新しいmaxが古いmaxなどよりも大きいかどうかを計算する必要がありますか？あなたがBFSを使用するかどうか聞いたので、最後に訪問した値は元のノードからの最大距離になります。つまり、すべてのことをする必要はありません。

Answer 1

各ノードからBFS n回を実行する必要があります。他のノードからbfsを実行するときには、ノードuからの距離はありません。vです。したがって、それらをすべて再計算する必要があります。

ここで、各ノードについて、vは、他のノードとの最大距離を保存します。グラフの直径はこれらの最大値の最大値です。

しかし、あなたのコメントから理解したように、一般的なグラフではなくツリーの問題を解決しています。木の場合、それはより簡単です。任意のノードからBFSを実行してくださいv。 から最も遠いノードを見つける。v;それをd1とする。今すぐノードd1からBFSを実行し、そこから最も遠いノードを見つけてください。それをd2とする。次に、d1からd2までのパスは、ツリーの1つ（その1つ）です。回答にはthisの質問の証拠があります。

これらの2つのBFSは、ゼロからすべての距離を計算しています。だから、BFSを2回実行するだけです。