有没有什么办法可以快速找到无向/有向图中的一个周期（后沿）的所有边？

我有一个最小生成树。我为它添加了一个边缘。当然会形成一个循环。我需要找到作为该周期一部分的所有边，即所有后边。可以做多快？我的解决方案 - 例如，如果它是边缘（1,4），请在所有位置向Adj（1）添加4，然后每次运行dfs。例如。如果Adj（1）有2,3,5，则在2之前先加4，运行DFS。我会得到回报。然后在2和3之间添加4并运行dfs。我得到了另一个后端。然后在3和5之间等等。有没有更快的方法来做到这一点？有没有什么办法可以快速找到无向/有向图中的一个周期（后沿）的所有边？

来源

2013-12-09 aandis

它被称为**循环**不是一个圆圈。只是FYI –

哦！对不起，这是一个错字！ – aandis

在树中，任何一对顶点之间都有单一（简单）路线。如果要添加边缘(i,j)，首先在i和j之间的树中找到路径，然后您将获得自己的循环 - 它由该路线中的所有顶点组成（并且一旦将(i,j)添加为边缘，就会变成循环）。

来源

2013-12-09 13:14:28

我认为一个dfs就足够了。 – aandis

任何类型的搜索都将用于查找树中一对顶点之间的单个路径。 BFS，DFS或任何其他正确的搜索。 –

我以不同的方式创建了我的邻接列表，并一直在看。所以这不只是在我脑海中流行！这很容易！谢谢！ :) – aandis

您正在寻找图形的强连通组件，可以使用Tarjan's algorithm（among others）找到。

来源

2013-12-09 13:13:03

我不认为强有力的连接组件将在这里帮助。这个问题有点神秘，但OP仅仅是寻找通过向树添加边来形成的循环（如果我理解正确的话）。 –

如果树中存在单个循环，则图的强连通组件将完全那个周期。 –

很难为无向图定义术语强连通组件。你什么意思？ –

有没有什么办法可以快速找到无向/有向图中的一个周期（后沿）的所有边？

回答

相关问题