Geek Answers Handbook

Algorithm for finding a path in a non-oriented tree

Suppose I have been given an undirected tree, and I need to find a path (single path) between two nodes.

What is the best algorithm for this. Maybe I could use Dijkstra's algorithm, but there is probably something better for trees.

C ++ example is useful but not needed

thank

+5
source share
3 answers

Suppose you have

struct Node
{
    std::vector<Node *> children;
};

what can be done is to cross the entire tree, starting from the root, keeping the entire chain during the traversal. If you find, for example, node1, then you save the current chain, if you find node2, then you check the intersection ... in the code ( UNTESTED ):

bool findPath(std::vector<Node *>& current_path, // back() is node being visited
              Node *n1, Node *n2,                // interesting nodes
              std::vector<Node *>& match,        // if not empty back() is n1/n2
              std::vector<Node *>& result)       // where to store the result
{
    if (current_path.back() == n1 || current_path.back() == n2)
    {
        // This is an interesting node...
        if (match.size())
        {
            // Now is easy: current_path/match are paths from root to n1/n2
            ...
            return true;
        }
        else
        {
            // This is the first interesting node found
            match = current_path;
        }
    }
    for (std::vector<Node *>::iterator i=current_path.back().children.begin(),
                                       e=current_path.back().children.end();
         i != e; ++i)
    {
        current_path.push_back(*i);
        if (findPath(current_path, n1, n2, match, result))
          return true;
        current_path.pop_back(); // *i
    }
    return false;
}
+1

, node , node. , . , std::map node.

UPDATE

, , . , , node # 1, node # 2. O (n) . , , , .

+6

, .

+1

More articles:


All Articles