I am solving a Leetcode problem called course-schedule II. In summary, we are given dependencies between courses and need to find the order in which they can be taken.
For example [1,0] [2,0] [3,1] [3,2]
Here [1, 0] indicates that to take course 1, we must first take 0 (second course is the prerequisite for first course).
The solution for this is a straight forward topological sort where we:
a) Create an adjacency list.
b) Create an indegree array/map
c) Do a DFS starting with the course which has an indegree of 0.
However, I messed up during the creation of adjaceny list. In my mind, the adjacency list should map Course => PreReq and therefore look like this:
1 -> [0]
2 -> [0]
3 -> [1, 2]
Turns out this won't work. Indegree tells me that 0 has no dependency so DFS starts with 0. And it will stop after 1 iteration as 0 has no adjacency mapping.
According to the solution, the adjacency list should be computed as PreReq -> Course
0 -> [1, 2]
1 -> [3]
2 -> [3]
So now when I start DFS with 0, I can then lookup the adjacency list of 0 -> [1, 2] and continue on. My question is PreReq -> Course doesn't make sense. In my mind, I read it as PreReq depends on Course. I would have never come up with it without seeing the answer.
Is there a template/idea/theory that tells us which way to make the adjacency map for a directed graph?
public class CourseSchedule2 {
//[0, 1], indicates that to take course 0 you have to first take course 1.
public List<Integer> findOrder( int[][] prerequisites ){
List<Integer> result = new ArrayList<>();
Map<Integer, List<Integer>> adjMap = createAdjacencyList( prerequisites );
System.out.println("Adjacency Map: " + adjMap);
Map<Integer, Integer> indegree = createIndegree( prerequisites );
System.out.println("Indegree: " + indegree);
Queue<Integer> queue = new ArrayDeque<>();
for( Map.Entry<Integer, Integer> entry : indegree.entrySet() ){
//In-degree value of 0 means this course has no pre-req
if( entry.getValue() == 0 ){
queue.add( entry.getKey() );
}
}
while( !queue.isEmpty() ){
Integer course = queue.poll();
result.add( course );
if( adjMap.containsKey(course)){
for( int neighbor : adjMap.get(course) ){
indegree.put(neighbor, indegree.get(neighbor) -1 );
if( indegree.get(neighbor) == 0 ){
queue.add(neighbor);
}
}
}
}
System.out.println(result);
if( result.size() == prerequisites.length ){
return result;
}else {
return Collections.emptyList();
}
}
public Map<Integer, Integer> createIndegree( int[][] courses ){
Map<Integer, Integer> indegree = new HashMap<>();
for( int[] course : courses ){
int courseToTake= course[0];
int preCourse = course[1];
indegree.put(courseToTake, 0);
indegree.put(preCourse, 0);
}
//Update indegree based on the course
for( int[] courseEntry : courses ){
int course = courseEntry[0];
indegree.put(course, indegree.get(course) + 1);
}
return indegree;
}
private static Map<Integer, List<Integer>> createAdjacencyList( int[][] prerequisites ){
Map<Integer, List<Integer>> adjMap = new HashMap<>();
for( int[] preq : prerequisites ){
int curCourse = preq[0];
int preCourse = preq[1];
adjMap.computeIfAbsent( preCourse, k -> new ArrayList<>()).add(curCourse);
}
return adjMap;
}
public static void main( String[] args ){
CourseSchedule2 tsort = new CourseSchedule2();
List<Integer> result = tsort.findOrder( new int[][]{
{1, 0},
{2, 0},
{3, 1},
{3, 2}
});
System.out.println("Result: " + result);
}
}
Is there a template/idea/theory that tells us which way to make the adjacency map for a directed graph?
I'd say you can express adjacency in any form that's required for the algorithms that use it. If direction matters (e.g. when using it with directed graph algorithms) it would normally be expressed as "source -> target", i.e. it should make it easy to follow the direction.
My question is PreReq -> Course doesn't make sense. In my mind, I read it as PreReq depends on Course.
That depends on how you define that "arrow" (->). You think of it as "depends on" but it could also be defined as "leads to". As you can see, those definitions are related to direction and which one is "better" depends on the way you intend to traverse:
Note that you could express the adjacency differently but that would make it harder to "follow the flow".
Let's make an example by expressing adjacency as int[][] with the values being the adjacent indices and doing "forward search" (from start to end)
List layout: PreReq -> Course (matching the traversal direction)
Finding the starting point(s): all indices that are not values in the adjacency list. So you need to iterate over the list at least once and "tick off" those indices that are mentioned as values (using a set or another array). Those that are left are your starting points. (Complexity: O(n))
Traversal to next node: it's as easy as int[] next = list[current] etc. (Complexity: O(1))
List layout: Course -> PreReq (against the traversal direction)
Finding the starting point(s): iterate over the list and look for those that don't have any PreReq values. (Complexity: O(n))
Traversal to next node: iterate over the list and get those that have the course as a prerequisite value. (Complexity: O(n))
Summary: as you can see the complexity for finding the starting point(s) is O(n) in both cases but if the list layout doesn't match the traversal direction complexity changes from O(1) to O(n) which can be significant.