algorithm - 强成分

Question

我正在尝试编写一个算法，它给出一个图 G 和 2 个节点“x”和“y”作为输入，它返回是否存在从“x”到“y”的循环路径

首先找到强连通分量然后检查 x 和 y 是否属于同一个强连通分量是一个好主意。
如果它们属于不同的连通分量，比如 x 属于 C1，y 属于 C2，那么如果存在从 C1 到 C2 的路径，那么我们可以说存在从 x 到 y 的循环路径。

Answer 1

我假设您也想多次计算具有“x”或“y”的路径。

如果 'x' 和 'y' 属于同一个强连通分量，则存在一条包含环的路径。（微不足道，根据强连通分量的定义）

但是，如果它们属于不同的强连接组件，则“y”应该可以从“x”到达，并且至少一个在路径上有节点的组件的大小必须大于 1。（在该组件中进行任何循环并继续沿路径）

如果是线性图，您的解决方案将失败。没有循环，但是您可以从属于不同强连接组件的“x”到“y”。

Answer 2

您使用强连接组件的想法应该可行。这是一个图表和一些代码供您试验：

首先，一个有向图：

它的邻接表表示：

13 vertices, 22 edges
0: 5 1
1: 
2: 0 3
3: 5 2
4: 3 2
5: 4
6: 9 4 8 0
7: 6 9
8: 6
9: 11 10
10: 12
11: 4 12
12: 9

它是强连接的组件：

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

现在，在实现 digraph 和 Kosaraju-Sharir 之后

class StronglyConnectedComponents
{
    private bool[] visited;
    private int[] componentIds;
    public int ComponentCount { get; private set; }

    public StronglyConnectedComponents(DirectedGraph graph)
    {
        visited = new bool[graph.VertexCount];
        componentIds = new int[graph.VertexCount];

        var order = new GraphTraversal(graph).ReverseOrder();
        var reversedGraph = graph.Reverse();
        foreach (var vertex in order)
        {
            if (!visited[vertex])
            {
                DepthFirstSearch(reversedGraph, vertex);
                ComponentCount++;
            }
        }
    }

    public int VertexComponentId(int vertex)
    {
        return componentIds[vertex];
    }

    public bool AreStronglyConnected(int source, int target)
    {
        return componentIds[source] == componentIds[target];
    }

    private void DepthFirstSearch(DirectedGraph graph, int vertex)
    {
        visited[vertex] = true;
        componentIds[vertex] = ComponentCount;
        foreach (var adjacent in graph.AdjacentTo(vertex))
        {
            if (!visited[adjacent])
            {
                DepthFirstSearch(graph, adjacent);
            }
        }
    }
}

class GraphTraversal
{
    private Stack<int> reversePostOrder;
    private bool[] visited;

    public GraphTraversal(DirectedGraph graph)
    {
        visited = new bool[graph.VertexCount];
        reversePostOrder = new Stack<int>();

        for (var vertex = 0; vertex < graph.VertexCount; vertex++)
        {
            if (!visited[vertex])
            {
                DepthFirstSearch(graph, vertex);
            }
        }
    }

    public IEnumerable<int> ReverseOrder()
    {
        return reversePostOrder;
    }

    private void DepthFirstSearch(DirectedGraph graph, int vertex)
    {
        visited[vertex] = true;
        foreach (var adjacent in graph.AdjacentTo(vertex))
        {
            if (!visited[adjacent])
            {
                DepthFirstSearch(graph, adjacent);
            }
        }
        reversePostOrder.Push(vertex);
    }
}

class DirectedGraph
{
    public int VertexCount { get; set; }
    public int EdgeCount { get; set; } = 0;

    private List<int>[] adjacencyLists;

    public DirectedGraph(int vertexCount)
    {
        VertexCount = vertexCount;
        InitializeAdjacencyLists(vertexCount);
    }

    public void AddEdge(int from, int to)
    {
        adjacencyLists[from].Add(to);
        EdgeCount++;
    }

    public IEnumerable<int> AdjacentTo(int vertex)
    {
        return adjacencyLists[vertex];
    }

    public DirectedGraph Reverse()
    {
        var reversedGraph = new DirectedGraph(this.VertexCount);
        for (var vertex = 0; vertex < this.VertexCount; vertex++)
        {
            foreach (var adjacent in this.AdjacentTo(vertex))
            {
                reversedGraph.AddEdge(adjacent, vertex);
            }
        }
        return reversedGraph;
    }

    public override string ToString()
    {
        String graghString = VertexCount + " vertices, " + EdgeCount + " edges \n";
        for (int vertex = 0; vertex < VertexCount; vertex++)
        {
            graghString += vertex + ": ";
            foreach (var adjacnet in this.AdjacentTo(vertex))
            {
                graghString += adjacnet + " ";
            }
            graghString += "\n";
        }
        return graghString;
    }

    private void InitializeAdjacencyLists(int vertexCount)
    {
        adjacencyLists = new List<int>[vertexCount];
        for (var vertex = 0; vertex < vertexCount; vertex++)
        {
            adjacencyLists[vertex] = new List<int>();
        }
    }
}

像这样的查询scc.AreStronglyConnected(2, 5)将告诉顶点之间是否存在有向循环。可运行代码在这里。