如何查找樹的任意兩個頂點之間的邊或頂點數？

它是一棵普通的樹（非循環圖），所以只能有一條這樣的路徑。我可以使用什麼算法？如何查找樹的任意兩個頂點之間的邊或頂點數？

編輯：

需要找到樹中的所有頂點對路徑

來源

2014-02-09 user3080029

你知道每個節點有多少信息？你存儲它的父母？當前樹級別？所以我們可以找到最有效的解決方案。 – piXelicidio

不，我不存儲任何此類信息。如果我存儲這些信息會有什麼幫助？ – user3080029

我會寫和回答假設你知道每個節點的父節點，做兩個簡單的迭代而不需要遞歸函數。 – piXelicidio

我想在此擴展@ templatetypedef的答案。

請注意，在您的問題中，您需要爲樹中每對節點至少執行一次寫操作。這些有n*(n-1)/2。
因此，就大O符號而言，找不到比O(n^2)運行更好的算法。

現在，使用DFS或BFS來查找每個節點的路徑。它將運行在O(n+m)（n頂點，m邊緣）。但由於它是一棵樹，我們知道m=n-1，給我們O(n)爲BFS/DFS。請注意，在來自某個節點v的單個BFS/DFS中 - 您爲每個節點u獲得d(v,u)。

如果您對每個節點重複一次，它會得到您O(n^2) - 這是最佳的大O符號。我確實同意你可以通過一些優化獲得更好的常量，但這只是關於它。

（1）開始它作爲評論，但它太長了，我覺得它值得回答。

來源

2014-02-09 18:34:15 amit

不錯。實際上，如果允許我們預先處理樹，然後支持個別距離查詢，問題會更加有趣。使用這個版本的問題，有一個O（1）查詢時間和只有O（n）空間的解決方案。 –

@Eyal - 我可以預處理樹。你有什麼建議？ – user3080029

@ user3080029：簡而言之，這個想法是將這個問題減少到LCA問題（最低公共祖先），該問題可以簡化爲RMQ（範圍最小查詢）。第一個縮減很簡單：如果你知道v1和v2的水平，以及他們的LCA節點u的水平，那麼d（v1，v2）= L（v1）+ L（v2）-2 * L（u）。第二個縮減比較複雜，在http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static中描述得非常好。但是，正如阿米特所說，如果您必須返回集合中的所有距離，則此方法沒有用處 - 請改爲使用簡單的DFS方法。 –

一個簡單的選擇是做一個深度優先搜索開始的一個節點，直到到達另一個節點。然後，您可以查看從第一個節點到第二個節點的路徑，它必須是這些節點之間的唯一路徑，然後計算該路徑中有多少條邊。這是線性時間運行的，因爲樹上的DFS只需要線性時間。

希望這有助於！

來源

2014-02-09 17:52:27 templatetypedef

爲每對頂點執行DFS將會過於耗時，難道你不這麼想嗎？ – user3080029

@ user3080029啊，我看到你已經編輯了這個問題。其實並不是那麼低效。看看阿米特的答案是爲什麼。 – templatetypedef

您需要查找Lowest Common Ancestor（LCA）。有不同的方法，你可以在這裏學習：http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

我已經使用了下游解決方案，因爲我不喜歡遞歸，這應該更好地解決您的問題，因爲您需要以高效的方式找到所有對。

enter image description here

1-）A之間尋找路徑 - > B： -Iterate從節點A往上標記每一個帶有標誌的每個父節點，直到母體根基金開始。 - 從節點B上行開始，直到找到標誌爲止。您已經找到LCA節點。 - 結果路徑是從A到LCA節點的列表，以及從B到LCA節點的反向列表。

2）改進發現A - > B： - 同時迭代兩個節點，標記A標記，B標記每個祖先節點。直到迭代發現B標誌或B迭代找到標誌。然後第一個找到另一個節點標誌找到了LCA節點。

3-）找到所有對路徑：您可以簡單地使用上面的解決方案爲每一對。或者嘗試考慮第一遍迭代所有樹創建標誌列表，然後第二遍確定每對的所有LCA節點，當節點的樹數量變得太大時，這將是不方便的。

來源

2014-02-09 19:54:59 piXelicidio

如果您選擇解決方案1）或2），您只需要兩個字段變量用於存儲兩個Flag節點，而不是解決方案3中所需的列表）。 – piXelicidio

如何查找樹的任意兩個頂點之間的邊或頂點數？

回答

相關問題