Coding Pattern: Topological Sort
Topological Sorting is the solution to the Precedence-constrained scheduling problems.
What is a Precedence-constrained scheduling?
Given a set of jobs to be completed, with precedence constraints that specify that certain jobs have to be completed before certain other jobs begun, how can we schedule the jobs such that they are all completed while still respecting the constraints.
In the below examples we have a bunch of courses which have their respective prerequisites courses. For e.g. The course “Linear Algebra” cannot be completed unless the course “Calculus” is completed first. Similarly to complete the course on “AI”, the courses “Algorithms” and “Introduction to CS” have to be completed first.
We can describe the above real life problem in terms of a graph as below.
Problem statement : Given a digraph (A directed acyclic graph), put the vertices in order such that all its different edges point from a vertex earlier in the order to a vertex later in the order (or report that doing so is not possible).
Note : For finding an order of completion using Topological Sort, the graph must be a acyclic directed graph. It means that there should not be a cycle present in the graph.
We will be using the algorithm called Kahn’s Algorithm to achieve the Topological sort.
I’ll use the below problem from Leetcode to explain the entire algorithm.
207. Course Schedule : https://leetcode.com/problems/course-schedule/
“numCourses” = 7
prerequisite array : [[1,0],[2,0],[4,1],[4,2],[5,2],[5,3],[6,4],[6,5]]
Steps:-
Represent the above problem in a graph structure. We will be using the “Adjacency List” data structure to model our graph. Here each index is represented as the key in a Map structure and its adjacent vertices as a list associated to the value of the Map.
Dictionary<int,List<int>> adjacencyList = new();
for(int i = 0 ; i < numCourses ; i++)
{
adjacencyList.Add(i,new List<int>());
}
for(int i = 0 ; i < prerequisites.Length ; i++)
{
adjacencyList[prerequisites[i][1]].Add(prerequisites[i][0]);
}Create an array called “indegree” which stores the indegree for each vertices. Indegree is the number of edges which point into a vertex. So for e.g. the indegree of vertex with index “6” is 2 since the edges from the vertex “4” and “5” point to it. We build this array by iterating over our adjacency list and incrementing the count whenever we encounter that index as a part of some incoming edge.
int[] indegree = new int[numCourses];
foreach(var item in adjacencyList)
{
foreach(int i in item.Value)
{
indegree[i]++;
}
}Using this “indegree” array we find the vertices which have zero indegree value. We will store these vertices in the queue called “indegreeZeroes”. This is done to find the start vertices since they do not have any prerequisites. We see that the only the vertices “0” and “3” have indegree zero and hence qualify to be our start vertices.
Queue<int> indegreeZeroes = new();
for(int i = 0 ; i < numCourses; i++)
{
if(indegree[i] == 0)
{
indegreeZeroes.Enqueue(i);
}
}Next, we will initialize a variable called “countOfCoursesVisited”. This variable will track the count of total courses visited. If the count of these visited courses and the count of “numCourses” variable do not match, it means that not all courses could be completed.
We will now “Dequeue” the vertices from the queue in a BFS manner so as to process the adjacent vertices. While dequeuing we will increase the count of “countOfCoursesVisited”. While doing so, for every neighboring vertices we visit, we will decrease the count of indegree for the same. This is to find the next set of “Start Nodes” to process. Once the indegree count of a vertex becomes zero that means that all the prerequisite courses for it has been completed and we can enqueue the same for the next processing.
int countOfCoursesVisited = 0;
while(indegreeZeroes.Count != 0)
{
int curr = indegreeZeroes.Dequeue();
countOfCoursesVisited++;
foreach(int i in adjacencyList[curr])
{
if(--indegree[i] == 0)
{
/* All the prerequisite courses for this vertex has been
completed and it is ready to be processed. */
indegreeZeroes.Enqueue(i);
}
}
}
return countOfCoursesVisited == numCourses;In the end we just compare the “countOfCoursesVisited” with “numCourses”. If the count is not same then we conclude that not all the courses can be completed hence we return false. Else we return true.
The complete code :
https://leetcode.com/problems/course-schedule/
public class Solution {
public bool CanFinish(int numCourses, int[][] prerequisites)
{
Dictionary<int,List<int>> adjacencyList = new();
for(int i = 0 ; i < numCourses ; i++)
{
adjacencyList.Add(i,new List<int>());
}
for(int i = 0 ; i < prerequisites.Length ; i++)
{
adjacencyList[prerequisites[i][1]].Add(prerequisites[i][0]);
}
int[] indegree = new int[numCourses];
foreach(var item in adjacencyList)
{
foreach(int i in item.Value)
{
indegree[i]++;
}
}
Queue<int> indegreeZeroes = new();
for(int i = 0 ; i < numCourses; i++)
{
if(indegree[i] == 0)
{
indegreeZeroes.Enqueue(i);
}
}
int countOfCoursesVisited = 0;
while(indegreeZeroes.Count != 0)
{
int curr = indegreeZeroes.Dequeue();
countOfCoursesVisited++;
foreach(int i in adjacencyList[curr])
{
if(--indegree[i] == 0)
{
indegreeZeroes.Enqueue(i);
}
}
}
return countOfCoursesVisited == numCourses;
}
}Some other problems which can be solved with this pattern:
210. Course Schedule II
https://leetcode.com/problems/course-schedule-ii/
In this problem we need to return the actual order of the courses which a student must take to complete all the courses.
The only addition we do in the code from the previous problem is the “List” data structure which we will populate as we process all the courses.
The complete code :-
public class Solution {
public int[] FindOrder(int numCourses, int[][] prerequisites)
{
// Initializing the adjency List with the length set as the total number of courses.
List<int>[] adjencyList = new List<int>[numCourses];
// Only additon from the previos normal Course Schedule problem
List<int> order = new List<int>();
for(int i = 0 ; i < numCourses ; i++)
{
adjencyList[i] = new List<int>();
}
for(int i = 0 ; i < prerequisites.Length ; i++)
{
// Adding the edge to the graph
// Its a directed graph so edges goes from course 1 to course 0 as
// in the problem statement its mentioned
//"For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1."
adjencyList[prerequisites[i][1]].Add(prerequisites[i][0]);
}
int[] indegree = new int[numCourses];
for(int i = 0 ; i < numCourses ; i++)
{
foreach(int j in adjencyList[i])
{
indegree[j]++;
}
}
Queue<int> queue = new Queue<int>();
for(int i = 0 ; i < indegree.Length ; i++)
{
if(indegree[i] == 0)
{
Console.WriteLine($"{i} is added to the queue for start nodes");
queue.Enqueue(i);
}
}
int nodeCount = queue.Count;
while(queue.Count != 0)
{
int temp = queue.Dequeue();
// Populating the processed course in this step
order.Add(temp);
foreach(int i in adjencyList[temp])
{
if(--indegree[i] == 0)
{
queue.Enqueue(i);
nodeCount++;
}
}
}
if(nodeCount != numCourses)
{
/* Since it is not possible to process all the courses
we will return an empty array*/
order.Clear();
}
return order.ToArray();
}
}1462. Course Schedule IV
https://leetcode.com/problems/course-schedule-iv/description/
In this problem we need to tell if one course is a prerequisite of another course. In this we will be populating the array “prereqList”. Querying this array will tell us in O(1) time if there is a relation between the two vertices.
To populate this “prereqList” we will do a BFS on every vertex. We will be storing every vertex that will be visited in the path from a certain start vertex.
Note : We will be storing the visited vertex in an array “visited”. This is to avoid reprocessing the already processed vertices again.
public class Solution {
Dictionary<int,List<int>> adjencyList;
bool[][] prereqList;
public IList<bool> CheckIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries)
{
adjencyList = new();
prereqList = new bool[numCourses][];
IList<bool> result = new List<bool>();
for(int i = 0 ; i < numCourses ; i++)
{
adjencyList.Add(i,new List<int>());
prereqList[i] = new bool[numCourses];
}
for(int i = 0 ; i < prerequisites.Length ; i++)
{
adjencyList[prerequisites[i][0]].Add(prerequisites[i][1]);
}
// Preparing the "prereqList"
for(int i = 0 ; i < numCourses; i++)
{
BFS(i,numCourses);
}
for(int i = 0 ; i < queries.Length ; i++)
{
/* Using the "prereqList" directly to check if there is
a relation or not */
result.Add(prereqList[queries[i][0]][queries[i][1]]);
}
return result;
}
private void BFS(int start,int numCourses)
{
Queue<int> queue = new();
queue.Enqueue(start);
bool[] visited = new bool[numCourses];
while(queue.Count != 0)
{
int temp = queue.Dequeue();
foreach(int i in adjencyList[temp])
{
if(visited[i] == false)
{
prereqList[start][i] = true;
visited[i] = true;
queue.Enqueue(i);
}
}
}
}
}This is the end of this article. Thanks for reading. Do clap and follow if you found this article helpful.
You can also show your appreciation by
Also checkout my other article on Union-Find Algorithm.
