計算樹中邊緣兩側的節點數量

Question

此處的樹意味着一個非循環無向圖，其中n節點和n-1邊緣。對於樹中的每個邊，計算其兩側的節點數。如果去掉邊緣，你有一個和b數量的節點兩棵樹，那麼我想找到這些值一個和b樹中的所有邊緣（最好是在O（n）的時間）。

直覺上我覺得從所有「葉」節點開始的多源BFS會產生答案，但我無法將其轉換爲代碼。

要獲得額外功勞，請提供適用於任何常規圖形的算法。

Answer 1

從任何節點運行深度優先搜索（如果您更喜歡廣度優先搜索）。 該節點將被稱爲根節點，並且所有邊將僅在從根節點開始的方向上遍歷。

對於每個節點，我們計算其有根子樹中的節點數。 第一次訪問節點時，我們將此數字設置爲1. 當子樹的子樹完全訪問時，我們將其子樹的大小添加到父樹。

在此之後，我們知道每個邊的一側的節點數量。 另一方面的數字只是總數減去我們找到的數字。

（你的問題的額外信用的版本包括在此之上尋找圖中的橋樑作爲一個不平凡的一部分，因此值得被問作爲一個單獨的問題，如果你真的有興趣。）

Answer 2

請注意，n=b-a+1。由於這個原因，你不需要計算邊的兩邊。這大大簡化了事情。從根開始的節點上的正常遞歸就足夠了。既然你的樹是無向的，你並沒有真正的「根」，只需選擇其中一片樹葉即可。

你想要做的是「向下」樹，直到到達底部。然後你從那裏倒數。葉返回1，並且每個遞歸步驟總和爲每個邊緣的返回值，然後通過遞增1

Answer 3

考慮以下樹：

1 
/\ 
    2 3 
/\ | \ 
5 6 7 8 

如果我們切節點1和2之間的邊緣，該樹一定會分裂成兩個樹，因爲是根據樹財產兩個節點之間只有一個獨特優勢：

1 
\ 
    3 
    | \ 
    7 8 

和

2 
/\ 
5 6 

因此，現在的a是植根於1的節點數量，而b是植根於2的節點數量。

> Run one DFS considering any node as root. 

> During DFS, for each node x, calculate nodes[x] and parent[x] where 
     nodes [x] = k means number of nodes of sub-tree rooted at x is k 
     parent[x] = y means y is parent of x. 

> For any edge between node x and y where parent[x] = y: 
      a := nodes[root] - nodes[x] 
      b := nodes[x] 

時間和空間複雜度均爲O(n)。