歡迎來踩本人博客
樹的直徑：
就是樹上最長路
方法 ：
求兩邊DFS即可

步驟：
1.從任意一點進行dfs，然后找到一個最長路徑，記錄最遠點u
2.然后從u再進行dfs，找最長路徑，記錄一點v。
（u，v）就是樹的直徑

證明：可以看這個視頻的第27：00（求樹直徑的原理和證明）

第四屆藍橋杯a組

證明：

我們可以看出圖中，樹的直徑是（4->2->5），長度為9.
我們一開始選定一個點dfs
如果是直徑外一點，比如w1，從w1進行dfs找到的就是點4，路徑就1->2->4，這個路徑一定會與樹的直徑相交，而找到的4是直徑的一端，那從4再進行dfs就是樹的直徑的另一端5，這樣兩遍dfs你就找到了樹的直徑
如果是直徑內一點，比如w2，從w2開始dfs找到的最遠點4，這個路徑會被包含在樹的直徑里，那找到的點也就是樹直徑的一端，再dfs就可以找到另一端。
綜上用兩遍dfs就可以找到樹的直徑

總結

以上是生活随笔為你收集整理的求树的直径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。