Python Ordenamiento topológico

Document 对象参考手册Ejemplos de Python3

Realizar un ordenamiento topológico de un grafo acíclico dirigido (Directed Acyclic Graph, abreviado DAG) G es organizar todos los vértices de G en una secuencia lineal, de modo que para cualquier par de vértices u y v en el grafo, si la arista (u, v) ∈ E(G), entonces u aparece antes de v en la secuencia lineal. Normalmente, dicha secuencia lineal se denomina secuencia que satisface el orden topológico (Topological Order), abreviada como secuencia topológica. En pocas palabras, obtener un orden total a partir de un orden parcial sobre un conjunto es lo que se denomina ordenamiento topológico.

En teoría de grafos, una secuencia compuesta por los vértices de un grafo acíclico dirigido se denomina ordenamiento topológico (en inglés: Topological sorting) de dicho grafo si y solo si cumple las siguientes condiciones:

  • Cada vértice aparece una y solo una vez;
  • Si A está antes que B en la secuencia, entonces no existe un camino de B a A en el grafo.

Ejemplo

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 ("Resultado del ordenamiento topológico:") g.topologicalSort()

Al ejecutar el código anterior, el resultado de salida es:

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

Document 对象参考手册Ejemplos de Python3

Otras extensiones