CODEWITHSUNDEEP
algorithmgraph-algorithmbacktracking
user2761895
user2761895

Reputation: 1541

Print all possible course schedules algorithm

This is famous course schedule question, but want to print out all possible course schedules.

Q: There are ‘N’ courses, labeled from ‘0’ to ‘N-1’. Each course can have some prerequisite courses which need to be completed before it can be scheduled. Given the number of courses and a list of prerequisite pairs, write a method to print all possible ordering of courses meeting all prerequisites. Assume that there is no cycle.

For the example in the main method, need to print [3, 2, 0, 1] [3, 2, 1, 0]

but my code prints only one of them [3, 2, 1, 0]

Backtracking is needed to make it work, but at some point my backtracking is wrong and not sure how to fix this since it keeps choosing the same order after backtrack. Once chose 1, 0 and then backtrack, it should choose 0, 1, but keeps choosing the same order 1, 0.

Can someone help me to make it work?

class AllCourseOrders {
  static Map<Integer, List<Integer>> map = null;
  static int[] visited = null;
  static int n = 0;

  public static void printOrders(int courses, int[][] prerequisites) {
    List<Integer> sortedOrder = new ArrayList<>();

    // init
    n = courses;
    visited = new int[courses];
    map = new HashMap<>();
    for(int i =0; i < courses; i++) 
      map.put(i, new ArrayList<>());

    // 1. build graph
    for(int[] pre: prerequisites) {
      int from = pre[0], to = pre[1];
      List<Integer> list = map.get(from);
      list.add(to);
    }

    // 2. dfs
    List<List<Integer>> results = new ArrayList<List<Integer>>();
    List<Integer> result = new ArrayList<>();

    for(Integer u: map.keySet()) {
      if(visited[u] == 0) {
        dfs(u, result, results);
        if(result.size() == n) {
          results.add(new ArrayList<>(result));
          result.remove(result.size()-1);
          visited[u] = 0;
        }
      }
    }

    results.forEach(res -> System.out.println(res));
  }

  static void  dfs(Integer u, List<Integer> result, List<List<Integer>> results) {
    visited[u] = 1;

    for(Integer v: map.get(u)) {
      if(visited[v] == 0 ) {
        dfs(v, result, results);
     }
    }

    visited[u] = 2;
    result.add(0, u);
  }

  public static void main(String[] args) {
   printOrders(4, new int[][] { new int[] { 3, 2 }, new int[] { 3, 0 }, new int[] { 2, 0 }, new int[] { 2, 1 } });
 }
}

Upvotes: 0

Views: 1080

Answers (1)

Eugene A.
Eugene A.

Reputation: 51

Your algorithm finds the first solution it can, not every single one. Every time you are presented with multiple vertices to take next (you can take different starting nodes, certain class you can take in any order), each choice will lead to a different result.

The course problem is simply trying to topologically sort a directed, acyclic graph. GeeksForGeeks provides the algorithm on their site in java, where the vertices are the courses and the edges are the prereqs.

Upvotes: 2

Related Questions