Topological Sort - https://www.clear.rice.edu/comp314/lec/week6/Topological.htm
Absent-minded professor Budimlić has a problem when getting ready to go to work in the morning: he sometimes dresses out of order: he�ll put his shoes on before putting the socks on, so he�ll have to take the shoes off, put the socks on and than the shoes back on. There�s also shirt, tie, belt, shorts, pants, watch and jacket that have to be put in a certain order. Can you help him? The order between different parts of clothing forms a graph: shorts before pants means there�s an edge between shorts and pants. Let�s do a DFS of this graph. The discovery (d) and finishing times (f) might be: Shorts: (1,10), pants(2,9), belt(3,6), jacket(4,5) ,shoes (7,8), socks (11,12), tie(13,14), watch(15,16), shirt(17,18). If we order the nodes based on the decreasing finishing time of the DFS, we get: shirt, watch, tie, socks, shorts, pants, shoes, belt, jacket. This is called topological sort. It works only on directed acyclic graphs. If the graph is cyclic, no topological order exists. Topological
Explore this link on the map →