Jac*_*ale 2 algorithm tree graph data-structures
在用于图的许多算法中,期望结果的连接通常存储在parent阵列中.
例如,在BFS或DFS,或最小生成树或最短路径中,我们存储每个顶点的父节点parent[].
我的问题是,如果我只有这样一个parent[],我怎样才能轻松获得任意顶点之间的路径,比如说,在O(n)中？请注意,无论是BFS还是DFS都没关系,重要的是parent[]我从中获得的图形算法.
如果其中一个顶点是另一个顶点的祖先,我可以很容易地得到路径,否则我只能parent[]从一个顶点追溯到根,再到另一个顶点再做一遍,然后检查它们的祖先是哪个祖先(到合并.这导致O(n ^ 2),因为我必须将一个顶点的每个祖先与另一个顶点的每个祖先进行比较以寻找合并点.
有人可以帮忙吗？
如果你使用大小为N的bool数组A,当你从顶点i到根时,你可以消除寻找合并点的复杂性,沿着路径标记每个顶点的A [i] = true.当你从顶点j到根时,如果A [i] == true,那就是合并点(第一个这样的顶点).