Bagaimana untuk melaksanakan algoritma pengisihan topologi menggunakan Python?

Bagaimana untuk melaksanakan algoritma pengisihan topologi menggunakan Python?

Isihan topologi ialah algoritma pengisihan dalam teori graf yang digunakan untuk mengisih graf akiklik terarah (DAG). Dalam pengisihan topologi, nod dalam graf mewakili tugas atau peristiwa, dan tepi terarah mewakili kebergantungan antara tugas atau peristiwa. Dalam hasil yang diisih, semua kebergantungan berpuas hati dan setiap nod disenaraikan selepas semua nod pendahulunya.

Melaksanakan algoritma pengisihan topologi dalam Python boleh diselesaikan menggunakan idea carian pertama mendalam (DFS). Berikut ialah contoh kod khusus:

from collections import defaultdict

class Graph:
    def __init__(self, num_vertices):
        self.graph = defaultdict(list)
        self.num_vertices = num_vertices

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

    def topological_sort_util(self, v, visited, stack):
        visited[v] = True

        for i in self.graph[v]:
            if visited[i] == False:
                self.topological_sort_util(i, visited, stack)

        stack.append(v)

    def topological_sort(self):
        visited = [False] * self.num_vertices
        stack = []

        for i in range(self.num_vertices):
            if visited[i] == False:
                self.topological_sort_util(i, visited, stack)

        sorted_list = []
        while stack:
            sorted_list.append(stack.pop())

        return sorted_list

# 测试代码
g = Graph(6)
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)

sorted_list = g.topological_sort()
print("拓扑排序结果：", sorted_list)

Kod di atas mula-mula mentakrifkan kelas Graf, yang merangkumi kaedah seperti menambah tepi dan pengisihan topologi. Semasa pengisihan topologi, carian pertama mendalam digunakan untuk merentasi nod dalam graf. Dengan menggunakan timbunan untuk menyimpan nod yang telah dilawati, anda akhirnya boleh mendapatkan senarai nod yang disusun mengikut peraturan susunan topologi.

Kod di atas juga mengandungi kes ujian mudah untuk mengesahkan ketepatan algoritma pengisihan topologi. Dalam kes ujian ini, graf bersaiz 6 ditakrifkan dan beberapa nod dan tepi ditambah. Akhir sekali, cetak senarai nod yang disusun secara topologi.

Menggunakan Python untuk melaksanakan algoritma pengisihan topologi boleh mengendalikan kebergantungan dalam graf dengan mudah, yang sangat membantu untuk isu seperti penjadualan tugas. Dengan memahami dan menggunakan algoritma ini, masalah praktikal boleh diselesaikan dengan lebih baik. Semoga artikel ini bermanfaat kepada anda.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma pengisihan topologi menggunakan Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!