c# - Tarjan循环检测帮助C#

这是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 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只是Vertex的列表。顶点具有代表边缘的其他顶点的列表。另外index和lowlink都初始化为-1

编辑:这正在工作...我只是误解了结果。

最佳答案

上面的内容实际上是正确的，我不明白什么是强连接的组件。我期望函数返回一个空列表，其中包含强连接的组件，但是它返回的是单个节点的列表。

我相信以上是可行的。如果需要，请随时使用!

关于c# - Tarjan循环检测帮助C#，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6643076/