Table of Content:
- What is a Graph?
- What is Topological Sort?
- Applications of Topological Sort
- Dressing like a Man(example)
- How to code
What is a Graph?
A graph is a simple non-linear data structure consisting of Nodes and Edges (Node are also referred to as Vertices). An edge connects a pair of nodes. Generally a graph is represented as G(u, v) where ‘u’ and ‘v’ are vertices.
In the below graph we have A,B,C,D,E vertices and edges connecting them.
This is a Directed Graph(edges are directed from one vertex to another).
I would like to give a simple intuition for topological sort. From the above graph let say the vertices represent a Task, and an edge represent dependency.
For Example an Edge (B, D) means ‘D’ has a dependency on ‘B’. This means that Task ‘D’ will only start once Task B is done.
Similarly ‘C’ has a dependency on ‘A’ and ‘B’(directed edges), so Task C will only start once Task ‘A’ and ‘B’ are done.
What is Topological Sort?
Topological sort is a linear sorting algorithm used in a Directed Acyclic Graph. In a graph G(u, v) topological sort will sort every possible edge (u, v) such that ‘u’ always comes before ‘v’ in sorting order.
Confused ? 🤔
Lets take an example:-
In above graph let take an edge (1, 2) . In Topological sorting ‘1’ will always be before ‘2’. Now apply this same approach on all the possible edges(u, v) where ‘u’ and ‘v’ are the vertices of the graph.
One possible topological sort would be 1, 3, 2, 5, 4, 7, 9, 6, 8
There can be many possible Topological sort orders but the key point is for every edge(u, v), u will always proceed v.
Applications of Topological Sort:
Topological sort is a very useful sorting algorithm and there are many applications of it:
- Prerequisite for a given courses- If a course have some prerequisite courses, and these courses also have some prerequisite than it would be best to represent it with a graph, where vertices are the courses and edges represent dependencies (or prerequisite of a given course).
Here topological sort will give you an order in which you should take a course (giving all the prerequisite of a given course).
- Build System- If a library have dependency on other libraries, and these libraries also have some dependencies, so the best way to represent this is with the help of a graph.
Here topological sort will give you an order in which you should build the libraries.
- Dressing like a man- Now this is what we will be looking for 😄
(but clearly there are many more useful applications of Topological sort).
The Graph should be a Directed “Acyclic” Graph (DAG):
This means that the graph should not have a cycle. If the graph have cycle than there won’t be any possible solution.
Lets take the prerequisite course example and see what’s wrong with having a cycle.
Above graph represent the prerequisite of different courses. Say I want to enroll in course 2, its prerequisite is course 1, whose prerequisite is course 4 & 5, course 4's prerequisite is course 3, whose prerequisite if course 2 😵.
(AND WE ARE STUCK IN A CYCLE)
We started with course 2 and ended at course 2. This means that practically I cannot take any course. This is why cycle should not be present in a graph for Topological sort.
Dressing like a Man:
Now with all the above discussion let take a look at how to dress like a man?
First we will have to create a graph of all the dependencies.
Below we have our graph with all the dependencies:-
In the above graph, shoes has dependencies on socks and pants.
This means, we cannot wear shoes without wearing socks or pants(which makes sense).
If we run topological sort on above graph we get one possible sorting order(dressing order).
shirt →tie →socks →watch →pants →shoes →belt →coat
And that is how you dress like a man 😎
How to write code for Topological Sort:
Writing code for topological sort is very simple. All you need to know is how to run Depth-first Search on a graph(if you don’t take a look at my previous post)
Steps to write code for topological sort:
- First perform DFS(G) on all the vertices.
- As each vertex is finished searching, insert it in front of a linked list.
- Print your linked list to get topological sort order.
And Voila!! Now you will have a possible dressing order.
Also check out the full code on my Github account below.