如果生成树和生成树上没有边缘，如何形成循环基础？
https://stackoverflow.com/questions/1612073
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我有一个带有Edge E和Vertex V的图表，我可以使用 Kruskal算法（或任何其他遍历 - 回溯 - 遍历 - 再次类型的算法），现在我想找到通过利用生成树和不在其上的边缘创建的所有循环基础树，允许我这样做的任何算法，除了暴力搜索？
当然，我可以从非生成树边缘的一个顶点开始，获取所有边缘，探索所有边缘，如果找到死角则缩回，直到我回到边缘的另一个顶点。但这有点，错误...残酷。还有其他想法吗？
解决方案
我们用于在图表中查找周期的简单算法：
创建深度优先生成树 每个节点都有父节点。 在遍历树时，创建已使用节点的记录。 当边指向先前使用的节点时，将其存储为a 循环边缘。 当生成树完成时，循环计数 edges给出了循环次数。 对于每个循环边缘递归通过两个节点的祖先 直到找到共同的祖先。那 将完全给出周期。
拥有循环边缘节点的所有祖先的索引（哈希表）可能很有用，这样可以快速找到共同的祖先。
我怀疑这是最好的算法，但速度相当快。
编辑以回复评论
生成树中的每个节点都有一个父节点。当到达循环边缘的节点时，它计算其祖先列表(List<Node>此列表可以为速度编制索引（即contains（）是< O(n))。当找到具有两个节点（n1, n2）的循环边缘时迭代n1, n1.ancestorList的祖先（快速自列表已经创建）并测试祖先是否在n2.ancestorList。如果它（commonAncestor）是，那么那些遍历的祖先就是对应于循环。然后迭代通过n2，直到你达到O(logN)（快速）。时间应该取决于循环边缘的数量，结合列表中的查找（可能<=>但便宜）。没有必要重新探索图表，有没有回溯。
其他提示
在构建生成树之后，迭代不在树中的每个边（A，B）并找到此边的节点的最低公共祖先（LCA），您的周期将是 A - <！> gt; LCA - <！> gt; B - <！> gt;甲
