如何查找树的任意两个顶点之间的边或顶点数？

它是一棵普通的树（非循环图），所以只能有一条这样的路径。我可以使用什么算法？如何查找树的任意两个顶点之间的边或顶点数？

编辑：

需要找到树中的所有顶点对路径

来源

2014-02-09 user3080029

你知道每个节点有多少信息？你存储它的父母？当前树级别？所以我们可以找到最有效的解决方案。 – piXelicidio

不，我不存储任何此类信息。如果我存储这些信息会有什么帮助？ – user3080029

我会写和回答假设你知道每个节点的父节点，做两个简单的迭代而不需要递归函数。 – piXelicidio

我想在此扩展@ templatetypedef的答案。

请注意，在您的问题中，您需要为树中每对节点至少执行一次写操作。这些有n*(n-1)/2。
因此，就大O符号而言，找不到比O(n^2)运行更好的算法。

现在，使用DFS或BFS来查找每个节点的路径。它将运行在O(n+m)（n顶点，m边缘）。但由于它是一棵树，我们知道m=n-1，给我们O(n)为BFS/DFS。请注意，在来自某个节点v的单个BFS/DFS中 - 您为每个节点u获得d(v,u)。

如果您对每个节点重复一次，它会得到您O(n^2) - 这是最佳的大O符号。我确实同意你可以通过一些优化获得更好的常量，但这只是关于它。

（1）开始它作为评论，但它太长了，我觉得它值得回答。

来源

2014-02-09 18:34:15 amit

不错。实际上，如果允许我们预先处理树，然后支持个别距离查询，问题会更加有趣。使用这个版本的问题，有一个O（1）查询时间和只有O（n）空间的解决方案。 –

@Eyal - 我可以预处理树。你有什么建议？ – user3080029

@ user3080029：简而言之，这个想法是将这个问题减少到LCA问题（最低公共祖先），该问题可以简化为RMQ（范围最小查询）。第一个缩减很简单：如果你知道v1和v2的水平，以及他们的LCA节点u的水平，那么d（v1，v2）= L（v1）+ L（v2）-2 * L（u）。第二个缩减比较复杂，在http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static中描述得非常好。但是，正如阿米特所说，如果您必须返回集合中的所有距离，则此方法没有用处 - 请改为使用简单的DFS方法。 –

一个简单的选择是做一个深度优先搜索开始的一个节点，直到到达另一个节点。然后，您可以查看从第一个节点到第二个节点的路径，它必须是这些节点之间的唯一路径，然后计算该路径中有多少条边。这是线性时间运行的，因为树上的DFS只需要线性时间。

希望这有助于！

来源

2014-02-09 17:52:27 templatetypedef

为每对顶点执行DFS将会过于耗时，难道你不这么想吗？ – user3080029

@ user3080029啊，我看到你已经编辑了这个问题。其实并不是那么低效。看看阿米特的答案是为什么。 – templatetypedef

您需要查找Lowest Common Ancestor（LCA）。有不同的方法，你可以在这里学习：http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

我已经使用了下游解决方案，因为我不喜欢递归，这应该更好地解决您的问题，因为您需要以高效的方式找到所有对。

enter image description here

1-）A之间寻找路径 - > B： -Iterate从节点A往上标记每一个带有标志的每个父节点，直到母体根基金开始。 - 从节点B上行开始，直到找到标志为止。您已经找到LCA节点。 - 结果路径是从A到LCA节点的列表，以及从B到LCA节点的反向列表。

2）改进发现A - > B： - 同时迭代两个节点，标记A标记，B标记每个祖先节点。直到迭代发现B标志或B迭代找到标志。然后第一个找到另一个节点标志找到了LCA节点。

3-）找到所有对路径：您可以简单地使用上面的解决方案为每一对。或者尝试考虑第一遍迭代所有树创建标志列表，然后第二遍确定每对的所有LCA节点，当节点的树数量变得太大时，这将是不方便的。

来源

2014-02-09 19:54:59 piXelicidio

如果您选择解决方案1）或2），您只需要两个字段变量用于存储两个Flag节点，而不是解决方案3中所需的列表）。 – piXelicidio

如何查找树的任意两个顶点之间的边或顶点数？

回答

相关问题