Hi, everyone.
So in this video, we are going to learn about topological saat and why topological art is important.
So in recent times, what is happening is companies started asking questions about topological thought.
They will not directly ask you to write the code for topological thought, explained a logical thought.
They will give you a statement and you have to think yourself that topological thought can be used here.
So what will it really look like?
So you will be given basically Dagg.
So what is that?
Bagis basically directed cyclic graph.
So they will give you are directed outside calligraphy and they will ask you to print something, to
output something, and you need to figure out whether topological so can be used or not.
So the example can be you want to install one software.
Let's say the name of the software is software if you want to install software.
But this software five has a dependency on software for that means before installing Software five,
you need to install software for and software five depends on software for.
So that's why this arrow this directed at.
All right.
I'm explaining myself again to install software, if it requires prerequisite, is that you must install
software for to install software for the prerequisite is that you must install software three.
To install software three, you must install Software zero, prerequisite is that you must have software
zero four for not only software three, you need one more software.
One more prerequisite is there that you need software to to install software to.
The prerequisite is that you must have software one with you.
Similarly, Software five not only depends on software for it also depends on software three.
So that's the problem statement I'm repeating myself.
We want to install software five and the prerequisite is that you must have software for it and software
to be installed.
OK, for software for the prerequisite is that you must have software installed and software to install
the OK for installing software to.
The prerequisite is that you must install software for installing software three.
The prerequisite is that you must install software zero and the software one and software zero.
They are basically independent.
They can be installed independently, right.
They do not have any other prerequisite.
So now the question is you need to print the order.
You need to print the order in which you will install the software.
Right.
You need to print.
You need to figure out.
You need to figure it out.
And you need to print the order in which you will be installing the software.
If you will directly install Software five, the installation will fail.
It will take three and four not present.
If you directly install software for it will say it will fail and it will say software tool and software,
not phone.
If you install software to it will say software were not found and it will fail.
Similarly, if you directly try to install software tree, it will fail and it will say software zero
not found.
So I hope you have understood the problem statement.
Right.
And what will be the order so you can install software zero first, then one, then two, then three,
then four and then five or the other order can be you can first install software one, then zero because
one and zero are basically independent.
Right.
Then you can install two, three, four and five.
The other order can be if you are installing one first then zero.
So when they are independent so they order doesn't matter.
Right.
You can install zero first or you can install one first or you can install zero first, then you can
install three to four, five because three and two, they are also independent.
They are not related to each other.
Right.
So you need to print this order.
You don't need to print any one of them.
All three are correct and there can be many more orders.
Right.
So what do you need to print any one of them?
You need to print any one of them.
And I think they will be one more order, which is possible.
That is zero and one zero one.
They are independent.
They can be installed.
Once 011 are installed, then you can install twenty eight.
Once zero is installed, you can install three.
Similarly, once software one is installed, you can install software two and two and three are installed.
So you can install software for once, software for any of the three and install it.
Then you can install software five.
So I think there are four possible ways in which we can install this software and we need to print any
one of them because all the files are correct so we can print any one of them.
I am explaining myself again, let's say for this example, Software Zero is independent so I can install
it.
Software one is an independent so I can install it so that he can be installed because of the zero is
installed in our software can be installed.
Software too can be installed because of the awareness there.
So you can install software to since we have software to software tree so we can install software for
correct.
Since we have software three and four installed so we can install software five.
Correct.
So all the orders are correct.
We just need to print any one of them.
And this graph, this graph is basically direct data graph and acyclic.
There is no cyclic present in this graph.
That means topological so can be used here.
So if you see this is basically one sorting order.
This is we can say this is basically one type of sorting only.
Right.
We are outputting inside Travie.
So that's where the name of the algorithm is topological and how this algorithm works.
So let's let's try to understand how the topological sort will give us the desired output.
So let's consider this example only.
So let me write it again here.
And then we will try to understand how the topological sort will work, so let's say I have I have one.
So for two.
Or the other way in which this problem can be fixed is basically, let me tell you so let's say for
doing for doing a course for and rolling in goes five.
You need to first complete goes for and you need to force complete goals.
Three Sokol's three and four are basically the prerequisite for enrolling in goals five, four and rolling
in goals for you need to first complete goals three as well as you need to first complete goals to.
For enrolling and completing course to unit first and rule and complete goals, one for completing,
three for enrolling and completing all three, you need to first complete and end all.
You need to first enroll and complete course zero.
Now the question is print the order in which you will enroll and complete the course.
So again, this is directed acyclic graph so topological.
So it will be used here and how topological sought will be used here.
So what will do given the graph, given a graph, first of all, we will find out in the gray area.
So we will populate one in the grey area in degree.
So for Vertex Zero, Vertex one, vertex two, vertex three, vertex four and Vertex five.
Let's try to bring in degree values.
So what do I mean by and degree.
So for this node, this, this, this, these are incoming arrows.
These are outgoing arrows.
So in degree is three, our degree is two.
So this is in degree for this node, which is three, because three arrows are directed towards this.
Two is basically our degree.
So two arrows are going out of it.
So that's why that's that.
That is our.
So we need to fill the in degree value for each of the vertex.
So given a graph we can figure out in degree, for example, forecourts zero in degrees, zero for course,
one in degree is zero for close to in degree is one for corsetry in degree is one four calls for in
degree is two four calls.
Five in degree is two.
Right.
So we can fill this in degree array because the graph is given to us so we can easily populate the values
here.
Correct.
So after filling the in degrees here, the main thing to notice is the main important point to notice
this problem is basically see the vertex that are having in degree as zero.
That means they are independent, they are independent, they can be picked up and completed late to
cause zero course when they have in degrees zero.
That means that do not they do not have any prerequisite.
You can directly enroll in this course and finish this course.
That is the main logic behind this problem, behind that of a logical thought.
So what you will do after figuring out the degree, you will maintain a queue.
And in this queue, this is curate a structure.
In this queue, you will only insert the vertex, which has zero degree, zero in degree.
Basically, this is what I will insert.
I will only insert those vertex which are independent vertex.
Which vertex?
The vertex, which are independent.
So in this case, Vertex Zero and one are independent.
So insert the zero, insert one because they are independent, the rest are dependent, still dependent.
They have, they are values are not zero degrees below zero.
So they are dependent.
Now what will do.
They will run a loop while the queue is not empty.
We will run a loop while the queue is not empty.
So pick the first node and remove it from here and your output will be here.
So pick the first node printed here.
And what we will do?
Go to all the neighbors of zero.
Let me write it here.
Go to all neighbours.
So go to neighbours.
It has only one neighbour, which is three.
It has only one neighbour which is three and reduce their in degree.
So go to three and reduce their in degree by one so it will become zero.
Why I am reducing the in degree because I have completed this thing, I have completed this thing.
So that's why I go to all the neighbours and reduce in degree by one.
So now the degree for three has become zero.
Zero means it is independent.
Independent means it should be present in the queue.
So I will insert in the queue now the next thing pick when printed here.
Go to all the neighbours of one, go to the neighbours of one two and reduce their in degree by.
So reduce what I will do, I am going to complete this course, so that's why I am reducing that degree
by seven so that degree will become zero.
Zero means independent.
Independent means it should be present in the queue because it can now be completed.
So it should be part of queue.
So push to indicate, you know, the next is basically three.
So big three painted here.
Go to the neighbors of three.
So three has two neighbors, four and five.
So reduce in degree by one because I am completed, I have completed corsetry.
So reduce in degree of four by one and five by one.
So it is still one.
So they are not independent, they are not independent means they will not be the part of the queue
right now.
Now the next element is to pick two.
I will complete.
I have enrolled in the course and I have completed this course.
So go to all the neighbors of two, which is neighbor four.
So reduce in degree by one it will become zero.
Zero means independent.
Independent means it can be.
It has to be the part of queue because I can complete I can enroll and complete this course now.
Right.
So four is now a part of.
Q So big four complete for go to all the neighbors of four and reduce their degree by one because I
have completed this course.
So Ford has only one neighbour which is five.
So reduce in degree by one it will become zero zero means independent.
Independent means it will be part of.
Q That is Bush five now big five from here complete five go to all the neighbours of five.
Five doesn't have any neighbour.
Now your queue becomes empty.
So since your queue becomes empty we are done.
And this is your output.
This is our output.
Which is correct.
Right.
This is our output.
Which is correct.
Now your output can change depending how you insert the elements in queue.
For example, 011, they both are independent, right?
They both are independent.
I inserted zero first, then I inserted one.
I could have done the reverse also.
If I inserted one, then I have inserted zero, then output might have been different.
Right, but the output will be correct for char.
So depending how you insert in the queue you will get different, different output.
You may or may not get one single output.
I mean, it may be possible that there is only one possible order.
There is only one possible order and there can be many possible order.
Right.
So any situation can be there.
So in case of when possible order, your output will be correct.
In case of many possible order, the topological sort will give you one of the order, the order in
which you will be inserting the elements in the queue.
So that is how topological works.
And this topological thought is really important because it is getting off in almost all of the interviews
now.
So be sure you've watched this video before, preparing for an interview.
So in the next video, we will be writing the pseudocode for the topological sort.
So I will see you in the next one.
Thank you.