Problem:
Given the number of courses to take in a class and the dependency of the courses (before taking one course you should have taken another course) find out if all the courses can be taken.
The dependency is mentioned by a list of pairs in the form [ [a1,b1],[a2,b2] …]
where to take the course a1 you should have completed the course b1
to take course a2 you should have completed the course b2 and so on..
For example, consider
the number of courses to be 2 , represented by 0 and 1
And the dependency given below:
[ [1,0] ,[0,1]]
Here to take the course 1 you should have completed the course 0
And to take the course 0 you should have completed the course 1
This creates a cyclic dependency and so you cannot take any of those courses.
Consider another example:
Number of courses : 3
Dependencies:
[[1,0] ,[ 2,1] ]
In this case you have to take course 1 after completing course 0
You have to take course 2 after completing course 1.
There is no cyclic dependency here .
So the answer is true.
Try out the solution here:
https://leetcode.com/problems/course-schedule/
Solution:
Hint :
– Use backtracking and Depth First Search
– Use Topological sort
Depth First Search with Backtracking
In this approach, you convert the dependencies of courses into a graph.
So if a course b has a dependency on course a,
then you represent the dependency as an outgoing edge from a to b, where a and b are represented as nodes of the graph .
You check for each vertex in the above graph by recursively traversing through each dependency and see if the original vertex is present in the path .
If it is present then there is a cycle and you return false .
We will first look into the code just with backtracking:
In this ,
You first represent the dependencies as a graph.
We will use map data structure for this .
The map has a key which represents the vertex of the graph (the course number) and the values represent the dependencies of the corresponding vertex ( courses which are dependent on this course)
So for the given prerequisites you prepare the graph .
Here is the code which does that :
Map < Integer, List < Integer >> nodes = new HashMap < > ();
for (int[] i: prerequisites) {
if (nodes.containsKey(i[1])) {
nodes.get(i[1]).add(i[0]);
} else {
List < Integer > relatives = new ArrayList < > ();
relatives.add(i[0]);
nodes.put(i[1], relatives);
}
}
Once you populate the graph , you iterate through the each vertex (course) and see if there is any cycle in it .
If there is a cycle you cannot complete the course .
The function to check the cycle is a recursive one.
Every recursive function has a base condition.
The base condition makes sure the function terminates at some point else it will keep invoking itself.
In this case the base condition is :
There exists a cycle
Or
There exists no cycle
To check if a cycle exists , you use a bitmap which keeps track of visited nodes / vertices in the graph.
When the same node is visited again you exit .
To check if there exists no cycle ,
You check if any nodes have dependencies on the current node .
If there is no node then there is no possibility of a cycle so you exit .
Here is that part of the code :
if (visited[courseNo]) {
return true;
}
if (!nodes.containsKey(courseNo)) {
return false;
}
Backtracking:
You check if a cycle exists through backtracking.
First you mark the current node as visited in a bitmap .
Then you recursively traverse through each node which are dependent on this node and see if you visit the original source node along the way .
If so there exists a cycle .
If there is no cycle you continue the backtracking for the next node.
For this you first revert the original node for which we did backtracking to unvisited so that it doesn’t affect the current backtracking.
Here is the backtracking code :
visited[courseNo] = true;
boolean ret = false;
List < Integer > relations = nodes.get(courseNo);
for (Integer i: relations) {
ret = isCyclic(i, nodes, visited);
if (ret) break;
}
visited[courseNo] = false;
Here is the entire code :
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer,List<Integer>> nodes = new HashMap<>();
for(int[] i:prerequisites){
if(nodes.containsKey(i[1])){
nodes.get(i[1]).add(i[0]);
}else{
List<Integer> relatives = new ArrayList<>();
relatives.add(i[0]);
nodes.put(i[1],relatives);
}
}
boolean[] visited = new boolean[numCourses];
for(int i=0;i<numCourses;i++){
if(isCyclic(i,nodes,visited)){
return false;
}
}
return true;
}
public boolean isCyclic(int courseNo,Map<Integer,List<Integer>> nodes,boolean[] visited){
if(visited[courseNo]){
return true;
}
if(!nodes.containsKey(courseNo)){
return false;
}
visited[courseNo] = true;
boolean ret = false;
List<Integer> relations = nodes.get(courseNo);
for(Integer i:relations){
ret = isCyclic(i,nodes,visited);
if(ret) break;
}
visited[courseNo] = false;
return ret;
}
}
In the above code we visit a node multiple times during backtracking.
If the there is no cycle starting from a node then we need not check the node and it’s descendant nodes while backtracking.
This check will improve time complexity.
We can do that using another bitmap.
So you add one more base condition to the function which checks for the cycle : if node is already checked , there is no cycle , so return false
Also at the end of the cycle check you mark the node as checked .
Here is the code along with the new change :
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer,List<Integer>> nodes = new HashMap<>();
for(int[] i:prerequisites){
if(nodes.containsKey(i[1])){
nodes.get(i[1]).add(i[0]);
}else{
List<Integer> relatives = new ArrayList<>();
relatives.add(i[0]);
nodes.put(i[1],relatives);
}
}
boolean[] visited = new boolean[numCourses];
boolean[] checked = new boolean[numCourses];
for(int i=0;i<numCourses;i++){
if(isCyclic(i,nodes,visited,checked)){
return false;
}
}
return true;
}
public boolean isCyclic(int courseNo,Map<Integer,List<Integer>> nodes,boolean[] visited,boolean[] checked){
if(visited[courseNo]){
return true;
}
if(checked[courseNo]){
return false;
}
if(!nodes.containsKey(courseNo)){
return false;
}
visited[courseNo] = true;
boolean ret = false;
List<Integer> relations = nodes.get(courseNo);
for(Integer i:relations){
ret = isCyclic(i,nodes,visited,checked);
if(ret) break;
}
visited[courseNo] = false;
checked[courseNo] = true;
return ret;
}
}
Here is the combined algorithm:
1. Create a graph using map with the course number as key and the list of courses which are dependent on it as value
2. Initialise two bit maps one to keep track of visited nodes in a path (making a cycle) and another to keep track of checked nodes
3. For each course check if they are cyclic using backtracking as follows :
3.1 if the current course is duplicate in the path return true
3.2 if the current course doesn’t have dependents return false
3.3 if the current course is already checked return false
3.4 mark current course as visited (part of cycle)
3.5 for each dependent node check if they are cyclic and return true if yes
3.6 revert current course as not visited for further backtracking if there is no cycle so far
Approach 2: Topological Sort
If a graph can be topologically sorted , then there is no cycle in it.
We will use this idea to detect cycle in the graph representing the courses.
Topological sort is sorting the nodes in a graph such that if node a has a successor b (or in other words node b is dependent on node a ) then a should come first not b.
All predecessors should precede all corresponding successors.
Kahn’s algorithm is one of the algorithms which can be used to implement topological sort.
It goes like this:
- Prepare a list of nodes which have no incoming edges
- Put them in a queue
- Pop the top node out and find its successors.
- For each successor remove the current edge (subtract the incoming edges value)
- If as a result the successor node has no incoming edges put it back in the queue
- Continue popping the top node and removing edges as before
At the end of this exercise if the total edges removed is equal to the total number of dependencies then the graph is topologically sorted and there is no cycle.
Else there is a cycle and return false.
Implementation:
Data Structures:
To implement this in code, first lets create a data structure to represent the nodes and the graph.
To represent the node lets create a custom class Node
This class has two fields:
- incomingEdges – this represents the number of incoming edges to this node
- outgoingNodes – this represents the number of edges from this node / number of successor nodes
To represent the graph let’s use a map with the course number as key and the node as value.
We will also use a queue to do the topological sort.
So totally there are three major data structures used here:
The Node:
class Node{
int incomingEdges ;
List<Integer> outgoingNodes = new ArrayList<Integer>();
}
The Graph:
Map<Integer,Node> map = new HashMap<>();
The Queue:
LinkedList<Node> queue = new LinkedList<Node>();
The first step is preparing the graph by iterating the input prerequisites:
for(int[] i:prerequisites){
Node prevNode = getNode(i[1]);
Node nextNode = getNode(i[0]);
nextNode.incomingEdges += 1;
prevNode.outgoingNodes.add(i[0]);
}
public Node getNode(int value){
if(map.containsKey(value)){
return map.get(value);
}else{
Node node = new Node();
map.put(value,node);
return node;
}
}
We set the incoming edges and the outgoing nodes by traversing the prerequisites.
Once we prepare the graph , we need to look for nodes with incoming edges 0 and put them in the queue:
for(Integer i: map.keySet()){
Node node = map.get(i);
if(node.incomingEdges == 0){
queue.add(node);
}
}
The next step contains the major logic:
Pop the queue and remove the edge between the current node and its successors.
While doing so see if the successor nodes have no more incoming edges.
If so add them again to the queue and repeat the process.
Keep track of the edges removes during this step.
int totalEdges = 0;
while(!queue.isEmpty()){
Node n = queue.pop();
for(Integer i:n.outgoingNodes){
Node o = map.get(i);
o.incomingEdges -=1;
totalEdges +=1;
if(o.incomingEdges ==0){
queue.add(o);
}
}
}
At the end of this step , if the total number of edges removed is not equal to the total number of dependencies represented by the prerequisites array then there is a cycle so return false , else return true:
if(totalEdges != prerequisites.length){
return false;
}
return true;
Here is the total code:
class Node{
int incomingEdges ;
List<Integer> outgoingNodes = new ArrayList<Integer>();
}
class Solution {
Map<Integer,Node> map = new HashMap<>();
public boolean canFinish(int numCourses, int[][] prerequisites) {
for(int[] i:prerequisites){
Node prevNode = getNode(i[1]);
Node nextNode = getNode(i[0]);
nextNode.incomingEdges += 1;
prevNode.outgoingNodes.add(i[0]);
}
LinkedList<Node> queue = new LinkedList<Node>();
for(Integer i: map.keySet()){
Node node = map.get(i);
if(node.incomingEdges == 0){
queue.add(node);
}
}
int totalEdges = 0;
while(!queue.isEmpty()){
Node n = queue.pop();
for(Integer i:n.outgoingNodes){
Node o = map.get(i);
o.incomingEdges -=1;
totalEdges +=1;
if(o.incomingEdges ==0){
queue.add(o);
}
}
}
if(totalEdges != prerequisites.length){
return false;
}
return true;
}
public Node getNode(int value){
if(map.containsKey(value)){
return map.get(value);
}else{
Node node = new Node();
map.put(value,node);
return node;
}
}
}
Time complexity:
Let e represent the number of edges (dependencies)
Let n represent the number of nodes.
In both the approaches each node and each edge is traversed only once so the time complexity is O(n + e)
Space complexity:
For the approach 1,
We create a map to represent the graph whose space complexity is O( e + n) since the map has n keys for each node and all the corresponding values add up to the total number of edges which can be represented as e.
We create two bitmaps one to detect a cycle and another to check if the node has already been checked or not . So the space complexity here is O( n + n)
We also make a recursive call to detect a cycle which can take maximum O(n).
In total , the space complexity is O( n + e)
For approach 2,
We create a graph using map data structure whose space complexity is O( n + e) again as it represents both the nodes and their edges.
We also create a queue which can have maximum n nodes
So overall space complexity is O( n + e)
Leave a Reply