Topological Sorting
Topological Sorting
Description:
Topological sorting is a sorting method to list the vertices of the graph in such an order that for every edge in the graph, the vertex where the edge starts is listed before the vertex where the edge ends.
NOTE:
There is no solution for topological sorting if there is a cycle in the digraph . [MUST be a DAG]
Topological sorting problem can be solved by using
1. DFS method
2. Source removal method
DFS Method:
• Perform DFS traversal and note the order in which vertices become dead ends (popped order)
• Reverse the order, yield the topological sorting.
Example:
Apply DFS – based algorithm to solve the topological sorting problem for the given graph:
Source removal method:
• Purely based on decrease & conquer
• Repeatedly identify in a remaining digraph a source, which is a vertex with no incoming edges
• Delete it along with all the edges outgoing from it.
Example:
Apply Source removal – based algorithm to solve the topological sorting problem for the given graph:
Comments
Post a Comment