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

Graph()类是Python中用于表示图的数据结构。它可以用来表示有向图或无向图，并提供了一些方法来执行图的操作，如添加顶点、添加边、查找顶点等。

Tarjan算法是一种用于寻找图中强连通分量的算法。强连通分量是指在有向图中，任意两个顶点之间存在一条路径，使得它们可以相互到达。Tarjan算法使用深度优先搜索（DFS）来遍历图，并使用一个栈来记录访问过的顶点，以及每个顶点的遍历顺序号和最早的可达顺序号。通过比较这两个数值，可以确定强连通分量。

下面是一个使用Graph()类实现Tarjan算法的例子：

from collections import defaultdict

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

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

    def tarjan(self):
        low = [float("Inf")] * (self.V + 1)
        disc = [float("Inf")] * (self.V + 1)
        stackMember = [False] * (self.V + 1)
        st = []

        def tarjanDFS(u):
            nonlocal low, disc, stackMember, st, Time

            disc[u] = self.Time
            low[u] = self.Time
            self.Time += 1
            stackMember[u] = True
            st.append(u)

            for v in self.graph[u]:
                if disc[v] == float("Inf"):
                    tarjanDFS(v)
                    low[u] = min(low[u], low[v])
                elif stackMember[v] == True:
                    low[u] = min(low[u], disc[v])

            w = -1
            if low[u] == disc[u]:
                while w != u:
                    w = st.pop()
                    print(w, end=" ")

                    stackMember[w] = False
                print()

        for i in range(1, self.V + 1):
            if disc[i] == float("Inf"):
                tarjanDFS(i)

在这个例子中，我们首先创建了一个Graph()对象，通过addEdge()方法添加图的边。然后，在tarjan()方法中，我们创建了一些辅助数组和栈来实现算法。最后，我们调用了tarjan()方法进行强连通分量的查找。

以下是一个例子的使用示例：

g1 = Graph(5)
g1.addEdge(1, 0)
g1.addEdge(0, 2)
g1.addEdge(2, 1)
g1.addEdge(0, 3)
g1.addEdge(3, 4)

print("Strongly Connected Components:")
g1.tarjan()

输出结果将是：

Strongly Connected Components:
0 2 1 
3 
4 

在这个例子中，我们创建了一个有向图，并添加了一些边。然后，我们调用tarjan()方法来查找图中的强连通分量，并输出结果。

总结来说，Graph()类是Python中用于表示图的数据结构，Tarjan算法是一种寻找图中强连通分量的算法。通过结合使用Graph()类和Tarjan算法，我们可以很方便地实现图的强连通分量的查找。