在由邻接表表示的树中找到一个节点到另一个给定节点之间的路径

Question

在树中找到一个节点到另一个给定节点之间的路径，由[=12=表示]邻接表
编辑：树被给出为 n 个节点的非循环连接图，其中节点从 1 到 n
例如，如果当 n = 5 时，树的形式为：
1 4
4 5
3 2
4 2
我应该能够使用算法
找到任何 n 个节点之间的路径我可以用 C++ 和 java 和 python

编程

Answer 1

你应该查阅 dijkstra 的 和 A* 路径查找算法，如果你的数据可以被操纵，它们会为你解决这个问题。

dijkstra的是我最喜欢的，简单易懂。但效率不如 A*
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

如果不知道您的数据是如何存储的、您使用的是什么编程语言或绘图软件，就无法真正给出更有用的答案，请添加标签并在您的问题中更具描述性。

希望对您有所帮助。

Answer 2

首先获取一个访问过的数组，并为所有节点将其初始化为0。将已访问数组中的起始节点标记为 1（即已访问），并在该节点上执行基本 DFS。一旦到达所需的节点，就停止算法。外勤局： http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/

Answer 3

您可以通过 BFS 或 DFS 来完成。这将花费 O(N) 时间。但是，如果您想查询 N 个节点中的任意 2 个，则可以使用 Heavy Light Decomposition 在线完成。

这是一个基于 BFS 的实现。

int n;
cin >> n;
vector <int> graph[n], visited(n);
for (int i = 0; i < n - 1; ++i)
{
    int st, en;
    cin >> st >> en;
    st--;
    en--;
    graph[st].push_back(en);
    graph[en].push_back(st);
}
int st, en;
cin >> st >> en;
st--, en--;
queue  <pair <int, int> > q;
q.push({st, 0});
visited[st] = 1;
while (!q.empty())
{
    auto  top = q.front();
    if (top.first == en)
        return top.second;
    q.pop();
    for (auto & x : graph[top.first])
    {
        if(!visited[x])
        {
            q.push({x, top.second + 1});
            visited[x] = 1;
        }
    }
}

在由邻接表表示的树中找到一个节点到另一个给定节点之间的路径

Find the path between a node to another given node in a tree represented by an adjacency list

java

python

c++

tree

adjacency-list