我的强连接组件算法错误

Question

我正在尝试在图中找到SCC，我编写的代码做得不错，但会犯一些小错误。

我尝试对算法进行一些小的调整，但最终只会使情况变得更糟。

public class Graph

{
    public int _verticesCount;
    public List<int>[] _vertexAdjancedVertices; // i-th element contains info about all adjanced vertices of vertex #i

    public Graph(int[,] edges)
    {
        _verticesCount = Program.Nkamers + 1;
        _vertexAdjancedVertices = new List<int>[_verticesCount];
        for (int i = 0; i < _verticesCount; ++i)
            _vertexAdjancedVertices[i] = new List<int>();
        for (int i = 0; i < edges.GetLength(0); ++i)
            Addedge(edges[i, 0], edges[i, 1]);
    }

    public void Addedge(int vertex1, int vertex2)
    {
        _vertexAdjancedVertices[vertex1].Add(vertex2);
    }
    public List<List<int>> GetStronglyConnectedComponents()
    {
        //DFS
        var processed = new bool[_verticesCount];
        var minConnectedValue = new int[_verticesCount];
        var sccCompleted = new bool[_verticesCount];
        int currentTime = 0;

        for (int startingVertex = 0; startingVertex < _verticesCount; ++startingVertex)
            if (!processed[startingVertex])
                GetStronglyConnectedComponents(startingVertex, ref currentTime, processed, minConnectedValue, sccCompleted);

        var res = minConnectedValue.Select((mcv, i) => new { Vertex = i, MinConnectedValue = mcv })
            .GroupBy(vmcv => vmcv.MinConnectedValue)
            .Select(g => g.Select(vmcv => vmcv.Vertex).ToList()).ToList();
        return res;
    }

    private void GetStronglyConnectedComponents(int vertex, ref int currentTime, bool[] processed, int[] minConnectedValue, bool[] sccCompleted)
    {
        processed[vertex] = true;
        ++currentTime;
        //var currentDiscoveryTime = currentTime;
        minConnectedValue[vertex] = currentTime; // initialize to current time
        sccCompleted[vertex] = false;
        foreach (var neighbour in _vertexAdjancedVertices[vertex])
        {
            if (!processed[neighbour])
            {
                GetStronglyConnectedComponents(neighbour, ref currentTime, processed, minConnectedValue, sccCompleted);
                minConnectedValue[vertex] = Math.Min(minConnectedValue[vertex], minConnectedValue[neighbour]); // if we will ever find cycle
            }
            else if (!sccCompleted[minConnectedValue[neighbour]]) // ignore references to completed sccs
            {
                minConnectedValue[vertex] = Math.Min(minConnectedValue[vertex], minConnectedValue[neighbour]); // we've reached processed vertex - use it as a minConnectedValue we could reach to (if smaller)
            }
        }
        if (minConnectedValue[vertex] == vertex) // we are going up to the stack, meaning that we are done with all the descendands
            sccCompleted[vertex] = true; // mark as completed in case if we are the root of current scc
    }
};

输入图为：

（1 4）
（1 5）
（2 3）
（2 1）
（3 2）
（4 3）
（5 7）
（5 6）
（6 8）
（8 12）
（7 9）
（9 7）
（9 11）
（9 10）
（10 8）
（10 7）

SCC应该是：(1,2,3,4)(5)(6)(7,9,10)(8)(11)(12)

我的结果是： (1,2,3,4)(5)(6,8)(7,9,10)(11)(12)

Answer 1

我不确定您的实现有什么问题，因为我不知道它采用哪种算法。我认为是 Tarjan 的，但可能是错的。无论如何，下面是“基于路径的强分量算法”的实现，我发现它更简单，无论如何代码更短。

public class Graph
{
    public Dictionary<int,List<int>>_adjacencyList; 

    public Graph(int[,] edges)
    {
        _adjacencyList = edges.Cast<int>().Distinct().ToDictionary(v => v, v => new List<int>());
        for (int i = 0; i < edges.GetLength(0); ++i)
            _adjacencyList[edges[i, 0]].Add(edges[i, 1]);
    }

    private void visit(int v , Stack<int> S, Stack<int> P, Dictionary<int, int> preorder, Dictionary<int, List<int>> components, ref int c)
    {
        preorder[v] = c++;
        S.Push(v);
        P.Push(v);

        foreach(var w in _adjacencyList[v])
        {
            if (!preorder.ContainsKey(w))
                visit(w, S, P, preorder, components, ref c);
            else if (! components.ContainsKey(w))
                while (preorder[P.Peek()] > preorder[w])
                    P.Pop();
        }

        if (v == P.Peek())
        {
            List<int> component = new List<int>();
            do {
                component.Add(S.Pop());
            } while (component.Last() != v);
            P.Pop();

            foreach (int i in component)
                components[i] = component;
        }
    }

    public List<List<int>> GetStronglyConnectedComponents()
    {
        var components = new Dictionary<int, List<int>>();
        var unassigned = new Stack<int>();
        var undetermined = new Stack<int>();
        var preorder = new Dictionary<int, int>();
        var counter = 0;

        foreach (int vert in _adjacencyList.Keys)
            if (!preorder.ContainsKey(vert))
                visit(vert, unassigned, undetermined, preorder, components, ref counter);

        return components.Values.Distinct().ToList();
    }
};


static void Main(string[] args)
{
    Graph g = new Graph(
            new int[,]
            {
                {1, 4 },
                {1 ,5 },
                {2 ,3 },
                {2 ,1 },
                {3 ,2 },
                {4 ,3 },
                {5 ,7 },
                {5 ,6 },
                {6 ,8 },
                {8 ,12},
                {7 ,9 },
                {9 ,7 },
                {9 ,11},
                {9 ,10},
                {10,8 },
                {10,7 }
            }
        );
    var output = g.GetStronglyConnectedComponents();
    foreach (var component in output)
        System.Console.WriteLine( "{" + String.Join(" , ", component) + "}");
}

以上内容直接改编自维基百科文章中的伪代码。运行时会产生以下结果：

{11}
{12}
{8}
{10 , 9 , 7}
{6}
{5}
{2 , 3 , 4 , 1}