Hello friends, my name is tushar and today I m going to talk about topological sort.
So given a directed acycle graph
topological sort is ordering
of vertices of this graph such that for every edge
u, v going from u to v, u should always appear before v in the ordering.
so for this graph here, one topological sort
could be A B C E D F G
another ordering could be
B D A C
E F and G
so the point here is that C should never appear be
A and B in the ordering or D should never be before B or E should never be
before C
and so on. So one of the application of topological sort
is in the build system. Suppose these were the
packages of a build system saying that
C has a dependency on A & B package and D has a dependency on B, E has dependency on C and so on
so how would build system know which package it should build first
so what it does is it builds a graph of packages and then applies topological sort
on them
like create one of these ordering and then
builds the packages in this
order so A & B build first, so C has dependency on A & B,
so then C can go next, and then E and D can go next
F can go next, and G can go next and so on
lets see how we are going to do topological sorting.
so we have 2 data structure set and stack
set has all the visited vertices while
stack has all the vertices in topological sorted order
so what we are gonna do is we are going to start from any node.
so lets say we started from E. So first thing we do is
E is not in visited
set we put E into the visited set so we put it here.
then we are going to explore the child of
E, children of E, so we go in direction of
H, so H is not visited so
we put H into the visited set and then we are going to explore children of
H, H has no children it means that H has been totally explored
at that point we put into the stack. So only when a vertex totally
explored it means that
all its children has been explored at that point you put that vertex into the
set, so I H into this stack.
then we go back to E and then E has another child F
and F is not in this visited set, so first we put into this visited set
and then we go to F and then F
has a child G so and G is not visited set so we first put it in the
visited said and then go to G and then at this point G doesn't have any
children
so G is we are done exploring G so we going to put G into
sorted stack so we will put G into the stack
and then we back to F and then F has
no children no more child to explore so we are going to put F
F into the stack and then we go back to E
explore all its children so we going to put E into the stack
so now what we are going to do is
we are going to pick
any other vertex which is not visited lets say we picked
B so first thing we do is put B to set
then we explore
a child of B so lets say we picked C C is not in the set visited set
so we gonna put C into the set then explore children of C C has
one child
E and E is already is into the visited set so we dont do anything
and then C has no other child at this point C into this
stack and then we go back to B
B has another child D and D is not in the visited set so we put
D into the visited set
and then we go to D and D has a child F
which is already in the visited set so we dont go there
and we stay at D and D has no more child to explore
so we put D into this stack and then we go back to B
at this B has explored both its children
so we are done exploring B so we put B into the stack
and at this point let's take another
unvisited node, the only unvisited node at this point is A so we go
to A
and put A into this visited set and then explore child of A
which is C, C is already into this visited set so we dont do anything about it
come back to A, A has no more children to explore
so we put A into this stack, so at this point
this stack has topologically sorted
order of vertices of this graph
so its A we pop elements one by one from this stack
A B D C
E F G
H remember there are multiple
topological sort orders possible for this graph
it's just the order in which you pick this vertices
decide which one of them will show up
but all of them have this property that if a vertex
if there is a vertex u and v going from u to v
u will always show up before we in this
ordering so in the next section lets quickly
look at the code. So the main function is topsort
in this I initialize a stack and a
a set and then we start iterating through the vertices of this graph
lets say first vertex I encounter is D so then
so I go into so visited doesnt contain D so I go into
topsortUtil
in topSortUtil
first thing I do is add D to the visited
then I explore neighbors of D so there is only one neighbor of D which is
F and visited doesn't contain F so we go into topsortUtil again
and go to top of topSortUtil in recursion
and again we add F to the visited and then
we explore neighbors of F
and F only has one neighbor G and it also is not there in visisted
we dont go into this
if condition we go here topSortUtil again top of this function topSortUtil
and in there we add to G to the
visited then we explore neighbors of G, G doesnt have any neighbor
so we are done exploring everything in G
so we put G into the stack then we roll back into recursion
and we reach topSortUtil where F was the vertex
and F is done exploring all its neighbours
so we add F to the stack and then we roll back in recursion
and similarly add D to the stack because D is done exploring
neighbours
then I let's say
and then we go back to this topSort here in the for loop
let's say we pick a another
vertex say B so B is
not in the visited so we again call topSortUtil with B
and then we going to topSortUtil first thing we do is we add
B into the visited and then explore neighbors of
B so lets say we explored C first so C is not in the visited so
call topSortUtil with C
and then we add C to the set
visited set and then C we explore Cs neighbors C has a neighbor D
and D is already in the visited so
we go continue into not explore this neighbor at all
go back to top of the for loop for C, C doesnt have any more
neighbors will break out of this for loop
and we add C to the stack then
we roll back in recursion and reach the point where vertex is
B and we were in this for loop B has another child
E and E is not in the visited so
we call topsortUtil as E as the vertex
and then go there so first thing we do is add E
into the visited set then we explore neighbors of
E E has only one neighbor F and F is
in the visited so we do continue and then go back to the top of the for loop
at this point E doesnt have any more neighbors to explore so it comes here
adds
E to the stack then we go back into the recrusion
to B so B has done exploring both its neighbors in the for loop
so it goes here and adds itself into the stack
at this point we go back to the top of this
topSort in here
we again iterate through vertices
if we encounter any other
vertex other than A then we will just continue because they are all in
visited
as soon as we hit vertex A its not in the visited so we call
topSortUtil here
add into the visited and then
we explore neighbors of A A has a neighbor C
but C is already in the visited so just do continue
at this point A doesn't have any other neighbors to explore so
we go to the stack and add into the stack and then
back to
top of topSort now we dont have any more vertex to
explore so we just return this stack
all you have to do is pop elements out of the stack and thats topological sorted
order so let me write that quickly A B E
C D
F and G this is all I have to talk about topological sort
please like this video share this video comment on this video checkout my
github link github.com mission peace interview wiki
check out my facebook page thanks again for
watching this video