我有一個問題，我需要在非二叉樹結構中找到最長的路徑。我不想回傳最長路徑的大小，我想回傳vector. 例如，在下面的圖片中
，我想找到最長的路徑并將其存盤在vector這樣的：{A,B,D,I,L}。我認為遞回是一種方法，但我不知道如何開始圍繞問題構建代碼。我將節點存盤在以下結構中：
std::unordered_map<std::string ID, Node> Node_data_;
struct Node
{
std::string id;
Name name;
std::vector<Node*> children;
Node* parent = nullptr;
};
uj5u.com熱心網友回復：
我不能評論，因為我的分數低于 50 分。這個天真的解決方案也很天真，哈哈。
但這是我的兩分錢:) 我希望你能從中得到一些東西:)
達到最長長度后，為什么不再次運行該演算法，但是這次計算長度，如果累積長度等于最大長度，則表示您找到了正確的路徑，從那時起，到此為止。
bool recur(node_info, int length, std::vector<std::string>& vs) {
...
if(length == max_length) {
return true;
}
for (neighbor nodes of this current node)
{
bool haveFound = recur(next_node,length next_node_length, vs);
if(haveFound) {
vs.push_back(next_node);
return true;
}
}
}
您可以修改代碼，使其不僅在它找到的第一個最大長度處停止，而且繼續耗盡樹中的所有節點。
uj5u.com熱心網友回復：
這是一個簡單的想法，它應該非常有效。如果您可以使用節點串列來回傳最長鏈會更有效。
std::vector<std::string> longest_path(const Node* node)
{
std::vector<std::string> best;
for (auto* child : node->children)
{
auto next = longest_path(child); // recurse
if (next.size() > best.size())
best = std::move(next); // keep the longest chain.
}
best.insert(best.begin(), node->id); // insert current node at begining of vector.
return best;
}
注意：我沒有嘗試編譯或運行代碼，但它應該能讓您很好地了解演算法的作業原理。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/363819.html
上一篇：如何對這個公式求模？
下一篇：動態規劃優化