困惑した課題について質問がありました。私はそれについてあまりにも一生懸命考えているかもしれません...質問は次のとおりです。
線形時間アルゴリズムを使用して、非巡回無向グラフ（つまり、ツリー）内の最長の重み付けされていないパスを決定します。
私の最初の意図はDFSを使うことです。しかし、DFSは、私が開始したノードから別の頂点までの最長のパスしか提供しないようです。ただし、問題はツリー内の最長のパスを要求します...私が開始したノードからの最長のパスではありません。誰かが私をまっすぐに設定できますか？
ありがとう。
そのような方法の1つは、任意のノードAを選択し、線形時間で他のすべてのノードまでの距離を計算することです。BがAから最も離れていると仮定します。ステップ2で、Bから最も離れているノードを見つけます。
d（P、Q）がPからQまでの距離を表すとします。EがA、B、Cの最も低い共通祖先である場合、d（A、B）= d（A、E）+ d（E、B ）また、d（E、B）≥d（E、C）であることに注意してください。
編集1：アルゴリズムまたは方法–任意のAから最も離れたBを見つけます。CがBから最も離れていることを見つけます。d（B、C）がグラフ内のすべての頂点ペアで最大であると主張する–は健全であるように見えますが、上記はそれを証明していません。
一方では、d（E、B）≥d（E、C）である必要はなく、他方では、それだけではd（B、C）≥d（F、G）を確立するのに十分ではありません。 F、Gはツリー内の任意のノードです。..。