2013-12-09 22 views
0

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

+0

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

+0

哦!对不起,这是一个错字! – aandis

回答

3

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

+0

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

+0

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

+0

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

0

您正在寻找图形的强连通组件,可以使用Tarjan's algorithmamong others)找到。

+0

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

+0

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

+0

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

相关问题