在樹上應用BFS找到兩個頂點

Question

之間的最長路徑在一棵樹我必須找到在它們之間具有頂點的最大數量的兩個頂點，包括兩者（連接）。然後我需要找到它們之間的頂點總數。我想用廣度優先搜索算法來處理這個問題，但沒有得到任何線索。如何處理這個？

示例（5個節點） - 樹鏈接：

1-2

1-3

3-4

3-5

則最長路徑是 2-1-3-4或2-1-3-5 因此該路徑具有總共4個頂點。

Answer 1

由於這是一棵樹，所以從任何源節點運行的BFS都會簡單地以您的源代碼作爲根返回相同的樹（對於通用圖形不如此，其中BFS可能會忽略在兩個節點之間創建較短路徑的邊你想比較）。

你想要兩個最遠的頂點，對於任何給定的根，這些頂點可能在不同的分支上（在這種情況下，你可以在每個布拉格上找到最遠的葉子），或者它們可以在同一分支上（在這種情況下你可以繼續在該子樹。但是這涉及到DP的一種形式，比單獨BFS稍多。

你可以試着運行單個BFS從任意root身份運行，加回邊（每個孩子分給爸爸），然後傳播回最長髮現葉子上的每個分支於母公司的一路攀升計算的方式，每個子樹的最大距離，如果家長有可用由於交叉分支距離更高dinstance - 取代當地最多

但是我不得不承認，在這一點上，與BFS的區別是相當大的。

Answer 2

最簡單的方法是使用鄰接矩陣。 的想法是使鄰接矩陣總5. 然後，導航每個矩陣，並找出最大該節點連接的節點的每個節點使得它作爲源節點，即在你的例子。將最大值的跟蹤路徑放入堆棧，以供將來使用。 重複這個過程直到你已經覆蓋了所有的矩陣。比較來自所有矩陣的結果。具有最大值的那個是可以選擇的值，並且其在堆棧中的相應值是給定的路徑。它也可以使用動態編程來解決。請參閱下面的鏈接，解釋Floyds Warshall算法。請參閱使用動態編程找到最短路徑的方式。你可以調整它的一部分，以找到解決你的問題使用DP。

http://www.youtube.com/watch?v=EMAoMMsA5Jg

-Bhupesh