從節點陣列和邊緣向量中獲取所有子樹的最有效方法是什麼？

Question

假設有節點作爲陣列和無向邊作爲載體是這樣的：

int nodes[n] = {1, 2, 3, ... ,n }; 
vector<pair<int, int>> edges; 

edges.push_back(std::make_pair(0, 2)); 
edges.push_back(std::make_pair(2, 4)); 

其中陣列中的每個元素是值和n是陣列的數目。遵循上面的代碼，有兩條邊。一個是從0到2.另一個是從2到4.這些數字表示數組的索引。在這種情況下，最大子樹的大小爲3，即0-2-4，最小子樹的大小爲1。

我解決了這個象下面這樣：

1. 排序edges矢量
2. 選擇在edges
3. 重複2一次置換，直到尋求所有可能的情況下

但是我不知道這是高效的方式。 如何獲取問題域中的所有子樹？有沒有一般的和有效的方法？

Answer 1

我使用基於邊緣信息的BFS（廣度優先搜索）解決了這個問題。爲了避免製作循環圖並將節點保存爲樹，我使用set。在搜索之前我也應用sort。減少時間複雜度是有用的。

void BFS(set<int> nodes, vector<pair<int,int>>& edges, vector<set<int>>& result) { 
    result.push_back(nodes); 
    int lastNode = *max_element(nodes.begin(), nodes.end()); 
    auto findIt = find_if(edges.begin(), edges.end(), [](const pair<int, int>& element){ return element.first == lastNode}); 
    if(findIt != edges.end()) { 
     nodes.insert((*findIt).second); 
     BFS(nodes, edges, result); 
    } 
} 

sort(edges.begin(), edges.end()); 

vector<set<int>> result; 
for(auto it : edges) { 
    set<int> nodes; 
    nodes.insert((*it).first); 
    nodes.insert((*it).second); 
    BFS(nodes, edges, result); 
}