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:

image

image

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:

image

Comments

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

Drawing Trees:HV-Layout