python 求给定邻接矩阵的强连通图

要求给定邻接矩阵的强连通图，可以使用Kosaraju算法。以下是一个用Python实现的示例代码：

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def DFSUtil(self, v, visited):
        visited[v] = True
        print(v, end=" ")

        for i in self.graph[v]:
            if visited[i] == False:
                self.DFSUtil(i, visited)

    def fillOrder(self, v, visited, stack):
        visited[v] = True

        for i in self.graph[v]:
            if visited[i] == False:
                self.fillOrder(i, visited, stack)
        
        stack.append(v)

    def getTranspose(self):
        g = Graph(self.V)

        for i in self.graph:
            for j in self.graph[i]:
                g.addEdge(j, i)

        return g

    def printSCCs(self):
        stack = []
        visited = [False] * (self.V)

        for i in range(self.V):
            if visited[i] == False:
                self.fillOrder(i, visited, stack)

        gr = self.getTranspose()
        visited = [False] * (self.V)

        while stack:
            v = stack.pop()
            if visited[v] == False:
                gr.DFSUtil(v, visited)
                print()

# 示例用法
g1 = Graph(5)
g1.addEdge(1, 0)
g1.addEdge(0, 2)
g1.addEdge(2, 1)
g1.addEdge(0, 3)
g1.addEdge(3, 4)

print("强连通分量为:")
g1.printSCCs()

这段代码首先定义了一个 `Graph` 类，其中 `addEdge` 方法用于添加边。`DFSUtil` 方法是深度优先搜索的辅助函数，用于遍历图中的顶点。`fillOrder` 方法用于填充顶点的遍历顺序。`getTranspose` 方法用于获取图的转置（即将边的方向反转）。`printSCCs` 方法是实现强连通分量的核心函数。

在示例中，我们创建了一个包含 5 个顶点的图，并添加了几条边。然后调用 `printSCCs` 方法来获取强连通分量。输出结果将显示强连通分量的顶点。