Python Topologische Sortierung

Document 对象参考手册Python3-Beispiele

Die topologische Sortierung eines gerichteten azyklischen Graphen (DAG) G besteht darin, alle Knoten in G in einer linearen Reihenfolge anzuordnen, sodass für jedes Knotenpaar u und v im Graphen gilt: Wenn die Kante (u,v)∈E(G) existiert, dann erscheint u vor v in der linearen Reihenfolge. Normalerweise wird eine solche lineare Reihenfolge als eine die topologische Ordnung erfüllende Sequenz bezeichnet, abgekürzt als topologische Sequenz. Einfach ausgedrückt: Aus einer partiellen Ordnung auf einer Menge eine totale Ordnung auf dieser Menge zu erhalten, diese Operation wird topologische Sortierung genannt.

In der Graphentheorie wird eine aus den Knoten eines gerichteten azyklischen Graphen zusammengesetzte Sequenz genau dann eine topologische Sortierung des Graphen genannt (Englisch: Topological sorting), wenn sie die folgenden Bedingungen erfüllt:

  • Jeder Knoten erscheint genau einmal;
  • Wenn A in der Reihenfolge vor B steht, dann gibt es keinen Pfad von B nach A im Graphen.

Beispiele

from collections import defaultdict class Graph: def __init__(self,vertices): self.graph = defaultdict(list) self.V = vertices def addEdge(self,u,v): self.graph[u].append(v) def topologicalSortUtil(self,v,visited,stack): visited[v] = True for i in self.graph[v]: if visited[i] == False: self.topologicalSortUtil(i,visited,stack) stack.insert(0,v) def topologicalSort(self): visited = [False]*self.V stack =[] for i in range(self.V): if visited[i] == False: self.topologicalSortUtil(i,visited,stack) print (stack) g= Graph(6) g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); print ("Ergebnis der topologischen Sortierung:") g.topologicalSort()

Die Ausgabe beim Ausführen des obigen Codes ist:

拓扑排序结果：
[5, 4, 2, 3, 1, 0]

Document 对象参考手册Python3-Beispiele

Andere Erweiterungen