How to write Tarjan algorithm in Python?

How to write Tarjan algorithm in Python?

Tarjan algorithm is a graph algorithm based on depth-first search (DFS), used to solve strongly connected component (SCC) problems. This article will introduce how to write the Tarjan algorithm in Python, with specific code examples.

The basic idea of ​​Tarjan's algorithm is to traverse the nodes in the graph through DFS, while recording the traversal sequence number and minimum reachable sequence number of each node. During the traversal, if there is a node with a smaller sequence number that the current node can reach, it is added to a temporary stack, and after the traversal is completed, it is judged whether the top node of the stack is the root node of a strongly connected component. If so, pop the nodes from the stack and add them to the result list.

The following is a code example of using Python to write the Tarjan algorithm:

def tarjan(graph):
    n = len(graph)
    index = [0] * n
    low_link = [0] * n
    on_stack = [False] * n
    stack = []
    result = []
    index_counter = 0

    def dfs(v):
        nonlocal index_counter
        index[v] = index_counter
        low_link[v] = index_counter
        index_counter += 1
        stack.append(v)
        on_stack[v] = True

        for w in graph[v]:
            if index[w] == -1:
                dfs(w)
                low_link[v] = min(low_link[v], low_link[w])
            elif on_stack[w]:
                low_link[v] = min(low_link[v], index[w])

        if low_link[v] == index[v]:
            scc = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                scc.append(w)
                if w == v:
                    break
            result.append(scc)

    for v in range(n):
        if index[v] == -1:
            dfs(v)

    return result

In the above code, a two-dimensional list graph is used to represent the adjacency relationship of the graph. graph[i] represents the set of vertices that can be reached by vertex i. The algorithm traverses each vertex iteratively, and if a vertex has not been visited, the DFS function is called to search. The DFS function uses a recursive method to implement the core logic of the Tarjan algorithm.

When using the Tarjan algorithm, just convert the adjacency relationship of the graph into a two-dimensional list graph, and then call tarjan(graph) to return the strongly connected component list of.

Summary:

This article introduces how to write the Tarjan algorithm in Python, and attaches specific code examples. By understanding the basic idea of ​​the Tarjan algorithm, we can better apply this algorithm to solve strongly connected component problems. I hope this article can help readers understand and use the Tarjan algorithm.

The above is the detailed content of How to write Tarjan algorithm in Python?. For more information, please follow other related articles on the PHP Chinese website!