的Tarjan周期检测帮助C＃ [英] Tarjan cycle detection help C#

问题描述

下面是一个工作的C＃实现的Tarjan的循环检测。

Here is a working C# implementation of tarjan's cycle detection.

该算法在这里找到： <一href="http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm">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 v.dependencies)
            {
                if (w.index < 0)
                {
                    strongconnect(w);
                    v.lowlink = Math.Min(v.lowlink, w.lowlink);
                }
                else if (S.Contains(w))
                {
                    v.lowlink = Math.Min(v.lowlink, w.index);
                }
            }

            if (v.lowlink == v.index)
            {
                List<Vertex> scc = new List<Vertex>();
                Vertex w;
                do
                {
                    w = S.Pop();
                    scc.Add(w);
                } while (v != w);
                StronglyConnectedComponents.Add(scc);
            }

        }

请注意一个DepGraph是顶点的只是一个列表。和顶点具有其他顶点从而重新present边缘的列表。另外指数和lowlink被初始化为-1

Note a DepGraph is just a list of Vertex. and Vertex has a list of other Vertex which represent the edges. Also index and lowlink are initialized to -1

编辑：这是工作......我只是misinter preTED结果

This is working...I just misinterpreted the results.

推荐答案

以上是实际上是正确的，我不明白什么是强连通分量了。我期待该函数返回的强连接组件空List，但它正在恢复单个节点的列表。

The above is actually correct, I did not understand what a strongly connected component was. I was expecting the function to return an empty List of strongly connected components, yet it was returning a list of single nodes.

我认为上述的工作。随意，如果你需要使用！

I believe the above is working. Feel free to use if you need it!

这篇关于的Tarjan周期检测帮助C＃的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！