Python Tri topologique

Document 对象参考手册Exemples Python3

Le tri topologique d'un graphe orienté acyclique (DAG) G consiste à disposer tous les sommets de G en une séquence linéaire, de telle sorte que pour toute paire de sommets u et v du graphe, si l'arête (u,v)∈E(G), alors u apparaît avant v dans la séquence linéaire. Habituellement, une telle séquence linéaire est appelée une séquence satisfaisant l'ordre topologique, abrégée en séquence topologique. En termes simples, obtenir un ordre total sur un ensemble à partir d'un ordre partiel sur cet ensemble, cette opération est appelée tri topologique.

En théorie des graphes, une séquence composée des sommets d'un graphe orienté acyclique est appelée un tri topologique du graphe (anglais : Topological sorting) si et seulement si elle satisfait les conditions suivantes :

  • Chaque sommet apparaît exactement une fois;
  • Si A est classé avant B dans la séquence, alors il n'existe aucun chemin de B à A dans le graphe.

Exemples

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 ("Résultat du tri topologique :") g.topologicalSort()

La sortie de l'exécution du code ci-dessus est :

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

Document 对象参考手册Exemples Python3

Autres extensions