Python Topological Sorting
Python3 ExamplesTopological sorting of a Directed Acyclic Graph (DAG) G is to arrange all vertices in G into a linear sequence, such that for any pair of vertices u and v in the graph, if edge (u,v)∈E(G), then u appears before v in the linear sequence. Usually, such a linear sequence is called a sequence satisfying the Topological Order, abbreviated as a topological sequence. Simply put, obtaining a total order on a set from a partial order on that set, this operation is called topological sorting.
In graph theory, a sequence composed of the vertices of a directed acyclic graph is called a topological sorting of the graph (English: Topological sorting) if and only if it satisfies the following conditions:
- Each vertex appears exactly once;
- If A is ranked before B in the sequence, then there is no path from B to A in the graph.
Examples
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 ("Topological sorting result:")
g.topologicalSort()
The output of running the above code is:
拓扑排序结果： [5, 4, 2, 3, 1, 0]Other Extensions