标签: tarjans-algorithm

这是tarjan循环检测的一个有效的C#实现.

该算法可在此处找到:http: //en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

public class TarjanCycleDetect
    {
        private static List<List<Vertex>> StronglyConnectedComponents;
        private static Stack<Vertex> S;
        private static int index;
        private static DepGraph dg;
        public static List<List<Vertex>> DetectCycle(DepGraph g)
        {
            StronglyConnectedComponents = new List<List<Vertex>>();
            index = 0;
            S = new Stack<Vertex>();
            dg = g;
            foreach (Vertex v in g.vertices)
            {
                if (v.index < 0)
                {
                    strongconnect(v);
                }
            }
            return StronglyConnectedComponents;
        }

        private static void strongconnect(Vertex v)
        {
            v.index = index;
            v.lowlink = index;
            index++;
            S.Push(v);

            foreach (Vertex w in …

我继续在Scala中实现了Tarjan的SCC算法的教科书版本.但是,我不喜欢代码 - 这是非常必要/程序化的,有很多变异的状态和簿记索引.是否有更多"功能"版本的算法？我相信算法的命令式版本隐藏了算法背后的核心思想,而不像功能版本.我发现其他人遇到了与此特定算法相同的问题,但我无法将他的Clojure代码转换为idomatic Sc​​ala.

注意:如果有人想要试验,我有一个很好的设置,可以生成随机图并测试你的SCC算法与运行Floyd-Warshall

我一直试图从维基百科学习Tarjan的算法3个小时,但我无法做出它的头或尾.:(

http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm#cite_note-1

为什么它是DFS树的子树？(实际上DFS会产生一个森林？o_O)为什么v.lowlink=v.index暗示这v是一个根？

有人可以向我解释这个/给出这个算法背后的直觉或动机吗？

根据维基百科的说法,我在Python中实现了Tarjan的强连接组件算法,但它无法正常工作.算法很短,我找不到任何区别,所以我不知道它为什么不起作用.我试图检查原始文件,但找不到它.

这是代码.

def strongConnect(v):
  global E, idx, CCs, c, S
  idx[v] = (c, c) #idx[v][0] for v.index # idx[v][1] for v.lowlink
  c += 1
  S.append(v)  
  for w in [u for (v2, u) in E if v == v2]:
    if idx[w][0] < 0:
      strongConnect(w)
      # idx[w] = (idx[w][0], min(idx[v][1], idx[w][1])) #fixed, thx
      idx[v] = (idx[v][0], min(idx[v][1], idx[w][1]))
    elif w in S:
      idx[v] = (idx[v][0], min(idx[v][1], idx[w][0]))
  if (idx[v][0] == idx[v][1]):
    i = S.index(v)
    CCs.append(S[i:])
    S = S[:i]

E = …

我正在尝试实现Tarjan的强连接组件(SCC)的迭代版本,这里为了您的方便而转载(来源:http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm).

Input: Graph G = (V, E)

index = 0                         // DFS node number counter 
S = empty                         // An empty stack of nodes
forall v in V do
  if (v.index is undefined)       // Start a DFS at each node
    tarjan(v)                     // we haven't visited yet

procedure tarjan(v)
  v.index = index                 // Set the depth index for v
  v.lowlink = index
  index = index + 1
  S.push(v)                       // Push v on the stack
  forall (v, v') …

我一直在研究关于它们的SCC和算法,我已经看到人们几乎总是提到Kosaraju的算法找到SCC并且还以(反向)拓扑排序对它们进行排序.

我的问题是:Tarjan的算法是否也找到(反向)拓扑排序？我发现它没有被提及(至少从我读过的地方,除了维基百科).

我一直在考虑它,并且非常有意义.当在某个节点u上调用tarjans_dfs时,可以在u的SCC之前找到所有可从u访问的SCC.我错了吗？

维基百科说它确实找到了它:

"虽然每个强连接组件中的节点顺序没有什么特别之处,但算法的一个有用属性是在任何后继组件之前不会识别出强连接组件.因此,强连接组件的顺序是确定的是由强连通分量形成的DAG的反向拓扑类型."

这是我的想法,还是更为人所知的是,Kosaraju的算法找到拓扑顺序而不是Tarjan也这样做的事实？

我正在阅读以下链接中的代码http://www.cosc.canterbury.ac.nz/tad.takaoka/alg/graphalg/sc.txt 我一直碰到“低链接”这个词，我没有知道这意味着什么。我知道这是一个相当菜鸟的问题，但有人可以向我解释一下吗？谢谢。

我正在研究用于强连接组件的 Tarjan 算法，它的工作方式对我来说很清楚。无论如何，有一行我不明白：

// Consider successors of v
for each (v, w) in E do
  if (w.index is undefined) then
    // Successor w has not yet been visited; recurse on it
    strongconnect(w)
    v.lowlink  := min(v.lowlink, w.lowlink)
  else if (w.onStack) then
    // Successor w is in stack S and hence in the current SCC
    v.lowlink  := min(v.lowlink, w.index) // *************
  end if
end for

我用星号标记了这条线。遇到back-edge时为什么要取节点的发现索引/时间

v.lowlink  := min(v.lowlink, w.index)

而不是仅仅抓住它的组件价值？

v.lowlink  := min(v.lowlink, w.lowlink)

我想不出这会成为问题的情况。

有人可以启发我吗？编辑：我怀疑这只是一个语义要求，即 lowlink …

我试图使用Tarjan算法确定有向图中的周期,该算法在1972年Septermber的研究论文"有向图的基本电路的枚举"中提出.

我正在使用Python来编写算法代码,并使用邻接列表来跟踪节点之间的关系.

所以在下面的"G"中,节点0指向节点1,节点1指向节点4,6,7 ...等.

G = [[1], [4, 6, 7], [4, 6, 7], [4, 6, 7], [2, 3], [2, 3], [5, 8], [5, 8], [], []]
N = len(G)

points = []
marked_stack = []
marked = [False for x in xrange(0,N)]

g = None
def tarjan(s, v, f):
    global g
    points.append(v)
    marked_stack.append(v)
    marked[v] = True

    for w in G[v]:
        if w < s:            
            G[v].pop(G[v].index(w))
        elif w == s:
            print points
            f = True
        elif marked[w] == False:
            if f …

我很难理解Tarjan的发音点算法。我目前在这里关注此教程：https : //www.hackerearth.com/practice/algorithms/graphs/articulation-points-and-bridges/tutorial/。我真正看不到的东西，以及在其他任何教程中都看不到的东西，正是“后边缘”的含义。考虑到此处给出的图形，我知道3-1和4-2是后边缘，但是2-1、3-2和4-3也是后边缘吗？谢谢。

我读了一篇关于 Tarjan 算法的文章， 博客。在这篇文章中，作者提出了一个问题：

第二种情况，我们可以用 low[v] 代替 disk[v] 吗？。答案是否定的。如果您能想到为什么答案是否定的，那么您可能已经理解了 Low 和 Disc 的概念。

我不知道为什么。当我在wiki上阅读类似的文章时，我发现代码可以是这样的：

     else if (w.onStack) then
    // Successor w is in stack S and hence in the current SCC
    v.lowlink  := min(v.lowlink, w.lowlink)

我想知道为什么作者说答案是否定的。谢谢回答我的问题。祝你有美好的一天。

这个问题与最近在这里提出的问题有关但又不同。

我刚刚阅读了维基百科伪代码。

algorithm tarjan is
  input: graph G = (V, E)
  output: set of strongly connected components (sets of vertices)

  index := 0
  S := empty
  for each v in V do
    if (v.index is undefined) then
      strongconnect(v)
    end if
  end for

  function strongconnect(v)
    // Set the depth index for v to the smallest unused index
    v.index := index
    v.lowlink := index
    index := index + 1
    S.push(v)

    // Consider successors of v
    for each (v, …

我有以下 Tarjan 算法的（递归）实现来查找图中的强连通分量，并且它工作正常：

public class StronglyConnectedComponents
{
    public static List<List<int>> Search(Graph graph)
    {
        StronglyConnectedComponents scc = new StronglyConnectedComponents();
        return scc.Tarjan(graph);
    }

    private int preCount;
    private int[] low;
    private bool[] visited;
    private Graph graph;
    private List<List<int>> stronglyConnectedComponents = new List<List<int>>();
    private Stack<int> stack = new Stack<int>();

    public List<List<int>> Tarjan(Graph graph)
    {
        this.graph = graph;
        low = new int[graph.VertexCount];
        visited = new bool[graph.VertexCount];

        for (int v = 0; v < graph.VertexCount; v++) if (!visited[v]) DFS(v);

        return stronglyConnectedComponents;
    }

    public void DFS(int v) …