Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Written by Prashant Basnet
Prashant Basnet, a software engineer at Unisala.com, focuses on software development and enjoys building platforms to share knowledge. Interested in system design, data structures, and is currently learning NLP
A sort that return a specific order of the vertex of a given a graph as long as the graph satisfies certain condition. This is a simple algorithm to learn.
First thing we need to look at is vertex at Isolation.
Every vertex in isolation has what's known as in-degree factor.
This is the key, graph needs to have edges that are directed in order to have this in degree value.
In degree value:
It's represented as how many connections are coming into this vertex. We want to start with vertex that has 0 because we're looking at a vertex in isolation.
So the easiest way to think about it is how many edges are pointing into this vertex
this is whatever the in-degree value for that vertex will be.
What it is is simply, when you get a graph that's directed, you want to figure out what every vertex's in-degree value is
The way topological sort works is that you can only take a vertex and it's value as long as its in-degree value is 0. But once you take it , then you want to remove it from the graph.
What that will do is, it will reduce the in-degree value of any nodes that it is directing into and then those nodes become open for us to take as a next value.
Topological sort does-not have very set order.
Here, we want to take the initial value of one of the vertex with in-degree of 0
This is one example of the topological order that we can get from that graph.
So when is topological sort not applicable?
There can be no cycle within this graph for us to perform a topological sort
If the graph contains a cycle, then it's impossible for us to get the value
The reason why is we can see this eg:
To figure out whether or not our directed graph is acyclic or a cyclic.
Once we finish our topological sort, if we are able to reach every single vertex, then it's a acyclic graph.
If we are not able to then, there must have been a cycle.
this note was taken from
https://www.udemy.com/
Let's solve a course schedule problem in leetcode that utilizes this Topological Sort
course-schedule/description/
bfs returns us the number of courses we can take: