Every graph has more than one topological sort sequence because it depends upon the in-degree of the edges of the nodes. The first starting node that we choose with an in-degree number of nodes is 0.
Let’s understand the topological sort algorithm with an example.
Step 1: We insert those nodes whose incoming edge count is equal to 0. So those nodes are node 1 and node 4.
Step 2:
a. We begin with Node 1. We can choose any node between Node 1 and Node 4.
b. We decrease every node edge by 1, which is connected to node 1. We are decreasing the edge of the nodes (0, 2, and 3).
c. We move Node 1 from the list to the topologically sorted list, as shown below.
Step 3:
a. We now proceed from the list, which is Node 4.
b. We decrease all the outgoing edges of the nodes connected to node 4, which are nodes (0 and 3).
c. Now, node 3 has no incoming edges, so we push it into the list, and node 4 shifts to the topologically sorted list.
Step 4:
a. We now proceed from the list, which is Node 3.
b. We decrease all the outgoing edges of the nodes connected to node 3, which are nodes (0 and 2).
c. Now, nodes 0 and Node 2 have no incoming edges, so we push it into the list, and node 3 shifts to the topologically sorted list.
Step 5:
a. We now proceed from the list, which is Node 0.
b. As no outgoing edges from Node 0, so we simply add them to the topological sort list.
Step 6:
a. We now proceed from the list, which is Node 2.
b. As no outgoing edges from Node 2, so we simply add them to the topological sort list.
Step 7:
Finally, we have sorted the list here.
Topological Sort Algorithm
The below are the steps for the topological sorting algorithm which we have to follow.
Step 0: Calculate the in-degree of each graph node.
Step 1: We first have to find a node that has incoming edges of zero.
Step 2: We remove that node from the graph and add it to the list of topological sorting orders.
Step 3: Remove those nodes that have outgoing edges.
Step 4: Reduce the in-degree by the number of related edges that were removed.
Step 5: Repeat Steps 1–4 until no nodes with 0 in-degree remain.
Step 6: Verify that all of the items are in the correct sequence.
Step 7: Now, we have sorted the order from Step 6.
Step 8: Put an end to the algorithm.
Python Code: The below is a python implementation of the above example.
classbuildGraph :
def__init__(self, nodes : int) :
self.nodes= nodes
# We are now storing the graph in adjacent list format
self.adjListDetails=defaultdict(list)
# It will stores the information about a particular node incoming
# edges in a graph
self.count_numbers_of_incoming_edge_of_a_node= []
# We stores the sorted nodes in topological order
self.topological_sorted_order= []
# We stores the information of all those nodes those don't
# have any incoming edges in a graph
self.nodes_have_zero_incoming_edges= []
# Now we are creating a adjacent list of all the graphs to sort
defAddGraphEdge (self, source :int, destination : int) :
self.adjListDetails[source].append(destination)
self.count_numbers_of_incoming_edge_of_a_node[destination] +=1
defTopologicalSortAlgorithm (self) :
for node inrange(self.nodes) :
ifself.count_numbers_of_incoming_edge_of_a_node[node] ==0 :
self.nodes_have_zero_incoming_edges.append(node)
whileself.nodes_have_zero_incoming_edges :
self.nodes_have_zero_incoming_edges.sort()
source =self.nodes_have_zero_incoming_edges.pop(0)
# adjacent list iteration
if source inself.adjListDetails :
for node inself.adjListDetails[source] :
self.count_numbers_of_incoming_edge_of_a_node[node] -=1
ifself.count_numbers_of_incoming_edge_of_a_node[node] ==0 :
self.nodes_have_zero_incoming_edges.append(node)
self.topological_sorted_order.append(source)
print("Topological Sorting Order : "+str(self.topological_sorted_order))
defmain() :
number_of_nodes=7
graph =buildGraph(number_of_nodes)
graph.count_numbers_of_incoming_edge_of_a_node= [0] *number_of_nodes
graph.AddGraphEdge(0,2)
graph.AddGraphEdge(0,5)
graph.AddGraphEdge(1,3)
graph.AddGraphEdge(1,6)
graph.AddGraphEdge(2,4)
graph.AddGraphEdge(3,5)
graph.AddGraphEdge(5,2)
graph.AddGraphEdge(5,4)
graph.AddGraphEdge(6,2)
graph.TopologicalSortAlgorithm()
if __name__ =="__main__" :
main()
Output:
| Topological Sorting Order : [0, 1, 3, 5, 6, 2, 4] |
Topological Sorting Algorithm Time Complexity:
The total time to process the algorithm is O (E + N), where E represents the number of edges and N represents the number of nodes in the graph. Then, in the following step, we must calculate each node’s in-degree, which generally takes O(E) times, and then place all of those nodes in a sorted list where their in-degree is zero, which takes O(N) times. So the total time complexity of the topological sorting algorithm is O (E+N).
But the space complexity of the topological sorting algorithm is O (N), which is the total number of nodes in the graph.
Application :
1. Topological sort is very useful for finding the graph’s cycle.
2. Topological sort algorithm is used to determine the deadlock conditions in an operating system.
3. Topological sort algorithm is used to find the shortest path in a weighted acyclic graph.
Conclusion:
This article has learned about one more important algorithm, topological sorting. We have seen that this algorithm only works with acyclic graphs. The topological sorting algorithm also helps determine the task compilation order. The topological sorting algorithm has many real-time advantages, like finding the shortest path. Because the topological sort is extremely useful, every programmer and student must thoroughly understand this algorithm.
