Топологическая сортировка в Python

Document 对象参考手册Python3 Примеры

Топологическая сортировка ориентированного ациклического графа (DAG) G заключается в упорядочивании всех вершин G в линейную последовательность таким образом, что для любой пары вершин u и v графа, если ребро (u,v)∈E(G), то u появляется перед v в линейной последовательности. Обычно такую линейную последовательность называют последовательностью, удовлетворяющей топологическому порядку, сокращённо — топологической последовательностью. Проще говоря, получение полного порядка на множестве из частичного порядка на этом множестве называется топологической сортировкой.

В теории графов последовательность, составленная из вершин ориентированного ациклического графа, называется топологической сортировкой графа (англ.: Topological sorting), если и только если она удовлетворяет следующим условиям:

  • Каждая вершина встречается ровно один раз;
  • Если A стоит перед B в последовательности, то в графе нет пути из B в A.

Примеры

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 ("Результат топологической сортировки:") g.topologicalSort()

Вывод выполнения приведенного выше кода:

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

Document 对象参考手册Python3 Примеры

Другие расширения