假设我有一棵无向树,并且我需要找到两个节点之间的路径(唯一的路径)。
最好的算法是什么?我可能可以使用 Dijkstra 算法,但对于树而言可能有更好的算法。
提供 C++ 示例会很有帮助,但不是必需的。
谢谢。
最好的算法是什么?我可能可以使用 Dijkstra 算法,但对于树而言可能有更好的算法。
提供 C++ 示例会很有帮助,但不是必需的。
谢谢。
假设你有
struct Node
{
std::vector<Node *> children;
};
那么可以做的就是从根节点开始遍历整个树,在遍历过程中保持整个链。如果您找到例如node1,则保存当前链,如果您找到node2,则检查交集...在代码中(未经测试):
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;
}