Bagaimana untuk menulis algoritma Tarjan dalam Python?

Bagaimana cara menulis algoritma Tarjan dalam Python?

Algoritma Tarjan ialah algoritma graf berasaskan carian pertama mendalam (DFS) yang digunakan untuk menyelesaikan masalah komponen bersambung kuat (SCC). Artikel ini akan memperkenalkan cara menulis algoritma Tarjan dalam Python, dengan contoh kod tertentu.

Idea asas algoritma Tarjan adalah untuk melintasi nod dalam graf melalui DFS, sambil merekodkan nombor jujukan traversal dan nombor jujukan minimum yang boleh dicapai setiap nod. Semasa traversal, jika terdapat nod dengan nombor jujukan yang lebih kecil yang boleh dicapai oleh nod semasa, ia akan ditambah pada tindanan sementara, dan selepas traversal selesai, ia dinilai sama ada nod atas tindanan adalah nod akar. daripada komponen yang bersambung kuat. Jika ya, pop nod dari tindanan dan tambahkannya pada senarai hasil.

Berikut ialah contoh kod untuk menulis algoritma Tarjan dalam Python:

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

Dalam kod di atas, senarai dua dimensi graf digunakan untuk mewakili hubungan bersebelahan graf. graf[i] mewakili set bucu yang boleh dicapai oleh bucu i. Algoritma berulang melalui setiap bucu Jika bucu belum dilawati, fungsi DFS dipanggil untuk mencari. Fungsi DFS menggunakan kaedah rekursif untuk melaksanakan logik teras algoritma Tarjan. graph来表示图的邻接关系。graph[i]表示顶点i所能到达的顶点集合。算法通过迭代遍历每个顶点，如果某个顶点未被访问过，则调用DFS函数进行搜索。DFS函数采用了递归的方式，实现了Tarjan算法的核心逻辑。

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

Atas ialah kandungan terperinci Bagaimana untuk menulis algoritma Tarjan dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!