Problem Solving Basis - Topological Sort
Updated:
How can we program the computer to wear socks first, and then shoes?
IdeaPermalink
Image from: http://personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/topoSort.htm
Topological Sort sorts the order. To sort something, we need something to compare. In this kind of problem, that order is given as priority. For example, socks and then shoes.
How ToPermalink
Data structurePermalink
Input is given in the form of “A should be done earlier than B”.
In this sense, we may think of structure something like:
A -> B -> C -> D ...
For this linked structure, we will use directed graph.
So our graph in adjacency list will be:
socks | -> shoes
undershorts | -> shoes -> pants
pants | -> shoes -> belt
shoes |
watch |
shirt | -> belt -> tie
belt | -> jacket
tie | -> jacket
jacket |
What should be done firstPermalink
Something that should be done first has no prior things to do.
In other words, If some task (like shoes) has prior things (socks) that should be done first, then that should not be done right now.
So, How can we think of the condition “no prior thing to do” in our graph data structure?
Right, Indegree of that node should be zero.
AlgorithmPermalink
Firstly, push the nodes with indegree of 0 to the queue.
Secondly, do the task.
Third, when task is done, delete the task, with its edges to other tasks. Repeat from the first.
Complexity AnalysisPermalink
Graph takes E edges, V vertices.
- Time: V nodes are into queue, and E edges are checked and deleted, so O(V+E)
- Space: O(E) for adjacency list
Template CodePermalink
cpp: https://github.com/dongminkim0220/Problem-Solvings/blob/master/templates/cpp/topological_sort.cpp
Leave a comment