Take a look at this problem here:
This seems like a simple problem that anyone can write some notes down and solve on their own. But is there a better way to do it? This is where Topological Sort comes in!
So what is topological sort? Let’s start with what we need to use it. To implement topological sort for our problem, we need to use a Directed Acyclic Graph(DAG) first. This is a graph in which the vertices do not cycle over each other.
An example would look something like this:
Now to use topological sort we need to do the following steps:
- Create an empty stack
- Loop through every vertex and on each one perform DFS
- After passing each vertex, add it to the stack
- Reverse the stack and return it
Here’s what it looks like using Python code:
Now to come back to our Course Scheduling problem, we can use this algorithm to determine the proper schedule for the student. Creating each course as vertices and order them. The steps for this is as follows:
- Find courses with no pre-reqs
- Take the next courses set by increasing pre-req count by 1
- Repeat until every course is taken
In summary, using topological sort in the right situation can help solve problems with efficiency! With the algorithm and code functions, using this method is the way to go.
