Comment écrire l’algorithme de Tarjan en Python ?

Comment écrire l'algorithme de Tarjan en Python ?

L'algorithme Tarjan est un algorithme graphique basé sur la recherche en profondeur (DFS) utilisé pour résoudre les problèmes de composants fortement connectés (SCC). Cet article expliquera comment écrire l'algorithme Tarjan en Python, avec des exemples de code spécifiques.

L'idée de base de l'algorithme Tarjan est de parcourir les nœuds du graphique via DFS, tout en enregistrant le numéro de séquence de traversée et le numéro de séquence minimum accessible de chaque nœud. Pendant le parcours, s'il existe un nœud avec un numéro de séquence plus petit que le nœud actuel peut atteindre, il est ajouté à une pile temporaire et, une fois le parcours terminé, il est jugé si le nœud supérieur de la pile est le nœud racine. d’un composant fortement connecté. Si tel est le cas, supprimez les nœuds de la pile et ajoutez-les à la liste des résultats.

Ce qui suit est un exemple de code d'utilisation de Python pour écrire l'algorithme de Tarjan :

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

Dans le code ci-dessus, une liste bidimensionnelle graph est utilisée pour représenter la relation d'adjacence du graphique. graph[i] représente l'ensemble des sommets pouvant être atteints par le sommet i. L'algorithme parcourt chaque sommet de manière itérative, et si un sommet n'a pas été visité, la fonction DFS est appelée pour effectuer une recherche. La fonction DFS utilise une méthode récursive pour implémenter la logique de base de l'algorithme Tarjan. graph来表示图的邻接关系。graph[i]表示顶点i所能到达的顶点集合。算法通过迭代遍历每个顶点，如果某个顶点未被访问过，则调用DFS函数进行搜索。DFS函数采用了递归的方式，实现了Tarjan算法的核心逻辑。

在使用Tarjan算法时，只需将图的邻接关系转化为二维列表graph，然后调用tarjan(graph)

Lorsque vous utilisez l'algorithme Tarjan, il vous suffit de convertir la relation d'adjacence du graphique en une liste bidimensionnelle graph, puis d'appeler tarjan(graph) pour revenir une liste de composants fortement connectés.

Résumé :

Cet article présente comment écrire l'algorithme Tarjan en Python et joint des exemples de code spécifiques. En comprenant l'idée de base de l'algorithme de Tarjan, nous pouvons mieux appliquer cet algorithme pour résoudre des problèmes de composants fortement connectés. J'espère que cet article pourra aider les lecteurs à comprendre et à utiliser l'algorithme Tarjan. 🎜

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!