Topological sorting of a Directed Acyclic Graph (DAG for short) G is to arrange all the vertices in G into a linear sequence such that 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.
Typically, such a linear sequence is called a sequence that satisfies a Topological Order, or topological sequence for short. Simply put, the operation of obtaining a full order on a set from a partial order on that set is called topological ordering.
In graph theory, a sequence of vertices of a directed acyclic graph is called a topological sorting (English: Topological sorting) of the graph if and only if the following conditions are satisfied:
- Each vertex appears and only appears once;
- If A precedes B in the sequence, there is no path from B to A in the graph.
sample code (computing)
from collections import defaultdict
class Graph:
def __init__(self,vertices):
= defaultdict(list)
= vertices
def addEdge(self,u,v):
[u].append(v)
def topologicalSortUtil(self,v,visited,stack):
visited[v] = True
for i in [v]:
if visited[i] == False:
(i,visited,stack)
(0,v)
def topologicalSort(self):
visited = [False]*
stack =[]
for i in range():
if visited[i] == False:
(i,visited,stack)
print (stack)
g= Graph(6)
(5, 2);
(5, 0);
(4, 0);
(4, 1);
(2, 3);
(3, 1);
print ("Topological ordering results:")
()
The output of executing the above code is:
Topological ordering results:
[5, 4, 2, 3, 1, 0]
Instance Extension:
def toposort(graph):
in_degrees = dict((u,0) for u in graph) # Initialize all vertex incidence to 0
vertex_num = len(in_degrees)
for u in graph:
for v in graph[u]:
in_degrees[v] += 1 # Calculate the incidence of each vertex
Q = [u for u in in_degrees if in_degrees[u] == 0] # Filter the vertices with incidence 0
Seq = []
while Q:
u = () #Delete from last by default
(u)
for v in graph[u]:
in_degrees[v] -= 1 #Remove all its pointers to
if in_degrees[v] == 0:
(v) # Filter again for vertices with incidence 0
if len(Seq) == vertex_num: # If there are vertices with non-zero incidence at the end of the loop it means that there is a ring in the graph and there is no topological ordering
return Seq
else:
print("there's a circle.")
G = {
'a':'bce',
'b':'d',
'c':'d',
'd':'',
'e':'cd'
}
print(toposort(G))
Output results:
['a', 'e', 'c', 'b', 'd']
To this point this article on Python on topological sorting knowledge points to explain the article is introduced to this, more related Python topological sorting content, please search for my previous articles or continue to browse the following related articles I hope you will support me more in the future!