How to find longest path in a non-binary tree and return it in a vector?-CodePudding

I have a problem where I need to find the longest path in a non-binary tree structure. I don't want to return the size of the longest path, I want to return the elements of the longest path in a vector. For example, in a following picture 1 I want to find the longest path and store it in a vector like this: {A,B,D,I,L}. I think recursion is a way to go, but I just can't get the idea how to start building the code around the problem. I am storing the nodes in a following structures:

std::unordered_map<std::string ID, Node> Node_data_;
struct Node
{
    
std::string id;

Name name;
    
std::vector<Node*> children;
    
Node* parent = nullptr;

};

CodePudding user response：

I can't comment because I have under 50 points. Also this naive solution is pretty naive, lol.

But this is my two cents :) I hope you get something out of this :)

After you have achieved the longest length, why not just run the algorithm again, but this time with a count of the length, and if the accumulative length is equal to the max length, it means you have found the right path, from then, just end at that.

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;
            }
    }
}

You can modify the code so that it not only stops at the first maximal length it finds but keep exhausting all nodes in the tree.

CodePudding user response：

Here's one simple idea, that should be quite effective. It would be more effective if you could use a list of nodes to retun the longest chain.

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(), id);  // insert current node at begining of vector.
    return best;
}

NOTE: I have not tried to compile nor run the code, but it should give you a good idea of how the algorithm works.