强成分

Question

我正在尝试编写一个算法，给定图 G 和 2 个节点 'x' 和 'y' 作为输入，returns 是否存在来自 [= 的循环路径15=] 到 'y'

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

Answer 1

我假设您还想多次计算具有 'x' 或 'y' 的路径。

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

但是，如果它们属于不同的强连通分量，'y' 应该可以从 'x' 到达，并且 至少一个在路径上有节点的分量的大小必须大于比一个。（采取该组件中的任何循环并继续路径）

如果是线性图，您的解决方案将失败。没有循环，但你可以从 '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

它是强连通分量：

现在，在实现有向图和 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)这样的查询会判断顶点之间是否存在有向循环。可运行代码是 here.

强成分

Strongly component

algorithm

graph

depth-first-search

strongly-connected-graph