Tarjan算法的伪代码

Tarjan算法是一种用于查找有向图中强连通分量的算法。以下是Tarjan算法的伪代码：

procedure TarjanAlgorithm(Graph graph):
    index = 0
    stack = empty stack
    for each vertex v in graph:
        if v.index is undefined:
            strongConnect(v, index, stack)

procedure strongConnect(vertex v, integer index, stack):
    v.index = index
    v.lowlink = index
    index = index + 1
    stack.push(v)
    v.onStack = true

    for each neighbor w of v:
        if w.index is undefined:
            strongConnect(w, index, stack)
            v.lowlink = min(v.lowlink, w.lowlink)
        else if w.onStack:
            v.lowlink = min(v.lowlink, w.index)

    if v.lowlink == v.index:
        newSCC = empty list
        repeat
            w = stack.pop()
            w.onStack = false
            newSCC.append(w)
        until w == v
        output newSCC

在这个伪代码中，我们首先定义了一个`index`变量来记录访问顺序，以及一个空栈`stack`来辅助寻找强连通分量。然后遍历图中的每个顶点，对于每个未访问过的顶点，调用`strongConnect`函数进行处理。

在`strongConnect`函数中，我们首先给顶点`v`分配一个索引`index`，并将其设为最低链接值`lowlink`。然后递增索引值，并将顶点`v`入栈，并设置`v.onStack`为真。

接下来，遍历顶点`v`的邻居顶点`w`。如果顶点`w`尚未被访问过，则递归调用`strongConnect`函数处理顶点`w`，并更新顶点`v`的最低链接值。如果顶点`w`已经在栈中，则更新顶点`v`的最低链接值。

最后，如果顶点`v`的最低链接值等于其索引值，则从栈中弹出顶点，并将其标记为不在栈中。重复此操作直到弹出的顶点为`v`，此时找到了一个强连通分量，将其输出。

希望这个伪代码可以帮助你理解Tarjan算法！