Wie implementiert man einen topologischen Sortieralgorithmus mit Python?

Wie implementiert man einen topologischen Sortieralgorithmus mit Python?

Topologische Sortierung ist ein Sortieralgorithmus in der Graphentheorie, der zum Sortieren gerichteter azyklischer Graphen (DAG) verwendet wird. Bei der topologischen Sortierung stellen Knoten im Diagramm Aufgaben oder Ereignisse dar, und gerichtete Kanten stellen Abhängigkeiten zwischen Aufgaben oder Ereignissen dar. Im sortierten Ergebnis sind alle Abhängigkeiten erfüllt und jeder Knoten wird nach allen seinen Vorgängerknoten eingestuft.

Die Implementierung des topologischen Sortieralgorithmus in Python kann mithilfe der Idee der Tiefensuche (DFS) gelöst werden. Das Folgende ist ein spezifisches Codebeispiel:

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)

Der obige Code definiert zunächst eine Graph-Klasse, die Methoden wie das Hinzufügen von Kanten und die topologische Sortierung umfasst. Bei der topologischen Sortierung wird eine Tiefensuche verwendet, um die Knoten im Diagramm zu durchqueren. Durch die Verwendung eines Stapels zum Speichern der besuchten Knoten können Sie schließlich eine Liste der Knoten erhalten, die nach topologischen Ordnungsregeln geordnet sind.

Der obige Code enthält auch einen einfachen Testfall, um die Richtigkeit des topologischen Sortieralgorithmus zu überprüfen. In diesem Testfall wird ein Graph der Größe 6 definiert und einige Knoten und Kanten hinzugefügt. Drucken Sie abschließend die topologisch sortierte Knotenliste aus.

Durch die Verwendung von Python zur Implementierung des topologischen Sortieralgorithmus können Abhängigkeiten im Diagramm problemlos verarbeitet werden, was bei Problemen wie der Aufgabenplanung sehr hilfreich ist. Durch das Verständnis und die Anwendung dieses Algorithmus können praktische Probleme besser gelöst werden. Ich hoffe, dieser Artikel ist hilfreich für Sie.

Das obige ist der detaillierte Inhalt vonWie implementiert man einen topologischen Sortieralgorithmus mit Python?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!