Topological Sorting for Interviews
Topological sorting is the ordering of vertices in a graph such that for a directed edge (u,v) (from vertex “u” to vertex “v”), the ordering of u is lower than that of v.
It is labelling of vertices of graph ‘G’ such that if F(v) is the ordering of vertex in a graph, then for (u,v) in G, F(u) < F(v)
For the above graph, the topological sort ordering will be : “ A B D C E F G H”
NOTE:
- There can be multiple orderings possible.
- Topological Sorting is only possible for Directed Acyclic Graphs. If there are cycle, then we cannot decide which vertex can be ordered first.
So how do we get the ordering? It is easy for us to just look at small graphs and come up with the ordering. But how do we convert that into an efficient code?
A simple approach
- start from nodes with no incoming edges i.e those nodes whose indegree is zero. Those nodes come first in the topological ordering.
- Then remove those nodes with indegree 0 from the graph and hence we further get some nodes with no incoming edges. Repeat this till there are no more nodes in the graph.
- Repeat 1 and 2 till there are no more nodes left.
If there are some nodes left but if they all have incoming edges, then it means that there is a cycle.
Example :
Consider the following graph:
- Indegree of B : 0
- Indegree of E : 1
- Indegree of C : 3
- Indegree of A : 1
- Indegree of D : 1
- Topological Order : [ ]
Since Indegree of B is 0, remove it and add it to the topological ordering and decrement the indegree of vertices with edges from B by 1.
- Indegree of E : 0
- Indegree of C : 2
- Indegree of A : 1
- Indegree of D : 1
- Topological Order : [ B ]
The indegree of E is 0, remove E from the graph and add it to topological ordering and decrease the indegree of of vertices with edges from E by 1.
- Indegree of C : 1
- Indegree of A : 0
- Indegree of D : 1
- Topological Order : [ B E ]
The indegree of A is 0, remove Afrom the graph and add it to topological ordering and decrease the indegree of of vertices with edges from A by 1.
- Indegree of C : 0
- Indegree of D : 0
- Topological Ordering : [ B E A]
Since both C, D do not have any incoming edges they can be added it to the topological ordering. The ordering of C,D doesn’t matter.
The final topological ordering is [ B E A C D]
Steps for writing the code:
- Calculate the indegree of all vertices.
- Append the nodes with indegree as 0 to topological ordering and decrease the indegree of all vertices with incoming edges from those nodes with indegree 0 by 1.
- Repeat Step 2 till there are no more nodes. If there are some nodes left but if they all have incoming edges, then it means that there is a cycle.
Time Complexity : O(M+N) where M is the number of edges and N is the number of nodes/vertices.
Applications of Topological Sorting :
Topological Sorting is very useful in cases of scheduling tasks with dependencies. An example can be installation of a particular program in your computer. That program may require other programs to be installed on your computer, topological sorting helps in handling such cases by checking if all dependecies are installed.
Questions involving topological sorting are also very frequently asked in interviews. One such question is “Alien Dictionary”.
Problem Statement :
Given a sorted dictionary (array of words) of an alien language, find order of characters in the language.
E.x: words=[“wrt”, ”wrf”, “er”, “ett” , “rftt” ]
output: [ w,e,r,t,f]
Solution:
Consider the words “wrt”, “wrf”. Since they appear in that order in alien dictionary we can deduce that “r” comes before “f” i.e (r->f)
Consider “wrf”, “er”. We can deduce that w comes before e in alien dictionary. Hence w->e
Consider “er”, “ett”, we get r->t
Consider “ett”, “rftt”, we get e->r
So we have:
- r->f
- w->e
- r->t
- e->r
We have dependencies, now using topological sorting we can easily get the ordering.
This problem was tagged as “Hard” on leetcode. But if we know the concept of topological sorting, then this problem is a cakewalk.
