Python中的Graph()实现强连通分量算法

在Python中，可以使用Graph()类来实现强连通分量算法。下面是一个使用例子：

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 DFS(self, v, visited):
        visited[v] = True
        for i in self.graph[v]:
            if not visited[i]:
                self.DFS(i, visited)

    def fillOrder(self, v, visited, stack):
        visited[v] = True
        for i in self.graph[v]:
            if not visited[i]:
                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 not visited[i]:
                self.fillOrder(i, visited, stack)

        gr = self.getTranspose()

        visited = [False] * (self.V)
        while stack:
            v = stack.pop()
            if not visited[v]:
                gr.DFS(v, visited)
                print()

在上面的例子中，我们首先实例化了一个Graph类，并使用addEdge()方法将连接的边添加到图中。

接下来，我们定义了一个DFS()方法，该方法使用深度优先搜索遍历图，并通过递归访问所有与给定节点v相连的未被访问过的节点。在DFS()方法中，我们将visited[v]设置为True，表明节点v已被访问。

然后，我们定义了fillOrder()方法，该方法使用DFS()方法并将节点添加到栈中。fillOrder()方法不会打印任何节点，而只是将节点添加到栈中。

接下来，我们定义了getTranspose()方法，该方法获取图的转置。它使用addEdge()方法将所有边反向添加到新的转置图中。

最后，我们定义了printSCCs()方法，该方法使用fillOrder()和getTranspose()方法打印所有的强连通分量。printSCCs()方法首先调用fillOrder()方法将所有的节点添加到栈中，然后获取图的转置，并将转置图的DFS()方法应用于栈中的节点。在DFS()方法中，如果节点v未被访问，则调用DFS()方法访问该节点，并打印该分量的所有节点。

以下是一个使用例子：

g = Graph(5) # 创建一个包含5个节点的图
g.addEdge(1, 0)
g.addEdge(0, 2)
g.addEdge(2, 1)
g.addEdge(0, 3)
g.addEdge(3, 4)

print("以下是图中的强连通分量:")
g.printSCCs()

在上面的例子中，我们首先创建了一个包含5个节点的图，并使用addEdge()方法添加了边。

然后，我们调用printSCCs()方法来打印图中的所有强连通分量。

输出结果为：

以下是图中的强连通分量:
4 
3 
0 2 1 

输出结果表示图中存在3个强连通分量，分别是节点4、节点3和节点0、节点2、节点1。