邊緣位於給定樹的多個頂點之間

Question

我有一棵樹，有N個頂點v1，v2，v3 .... vN。樹在vertex v1上被掛起。現在我在樹上選擇了一些隨機路徑。如何知道在所有這些選擇路徑上的樹中是否存在邊緣？

編輯 - 所有的路徑是雙向的。

Answer 1

正如G.Bach所建議的那樣，您遍歷每條路徑，並在此過程中爲每條邊記錄它包含在路徑中的次數。最後，您可以遍歷邊集，並且與路徑數相同的邊（或邊）將成爲所有選定路徑上的邊。

由於在樹中確切地有n-1邊緣，所以這個算法是O(n)，我猜是最高效了。