title: Python Graph BFS Coding Question: Generate Course Sequence
body: <p>I'm having trouble with a coding question. I have attempted a solution (see below), but am stuck on one part and would like suggestions.</p>
  
  <p>Question: Consider an academic program that consists of N courses. Some courses have others as prerequisites. For example, if course 2 is a prerequisite of course 3 you must finish course 2 before enrolling in course 3. You can attend only a single course at a time. Build a schedule to complete all courses in a linear sequence and to satisfy all prerequisites for every course. If more than one variant of possible schedule exists, use the schedule where courses with smaller indices are finished first.</p>
  
  <p>For example:</p>
  
  <pre><code>4
  1 0
  2 0
  3 1 2
  </code></pre>
  
  <p>The first row means that there are 4 courses in the academic program. The second and third rows define that course 0 must be taken before courses 1 and 2. And the fourth row defines that courses 1 and 2 must be taken before course 3.</p>
  
  <p>Output:
  A schedule containing a space-delimited list of courses, in the order of their attendance. For example:</p>
  
  <pre><code>0 1 2 3 
  </code></pre>
  
  <p>For this example, another schedule exists 0 2 1 3. But we must select the variant 0 1 2 3 where course 1 (with a smaller index) is attended before the course 2 (with a greater index).</p>
  
  <pre><code>Test 1
  Test Input
  4
  1 0
  2 0
  3 1 2
  Expected Output
  0 1 2 3
  
  Test 2
  Test Input
  7
  0 1 2
  1 3
  2 3
  3 4 5
  4 6
  5 6
  Expected Output
  6 4 5 3 1 2 0
  
  Test 3
  Test Input
  8
  4 0 2
  0 1 6
  2 3 7
  1 5
  6 5
  3 5
  7 5
  Expected Output
  5 1 3 6 0 7 2 4
  </code></pre>
  
  <p><strong>Solution Attempt:</strong></p>
  
  <p>I recognized this as just performing BFS on an undirected graph with the courses and prerequisites as edges connected to each other. </p>
  
  <pre><code>import collections 
  
  graph = collections.defaultdict(set)
  
  def add_edge_undirected(graph, u, v):
      if not (u in graph and v in graph[u]) or not (v in graph and u in graph[v]):
          graph[u].add(v)
          graph[v].add(u)
  
  def bfs(graph, root, ans): 
      visited, queue = set(), collections.deque([root])
      visited.add(root)
      while queue: 
          print(queue)
          vertex = queue.popleft()
          ans.append(vertex)
          for neighbour in graph[vertex]: 
              if neighbour not in visited: 
                  visited.add(neighbour) 
                  queue.append(neighbour)
  
  
  def main():
      inputs = [[4, 0, 2], [0, 1, 6], [2, 3, 7], [1, 5], [6, 5], [3, 5], [7, 5]] # test case 3
      start = 5 # we are starting from vertex 5 because that is the first course in the entire sequence
  
      for prereq in inputs:
          for i in range(1, len(prereq)):
              add_edge_undirected(graph, prereq[0], prereq[i])
  
      ans = []
      bfs(graph, start, ans)
      print(ans)
  
  main()
  </code></pre>
  
  <p>Sample Input: Test case 3. 
  Terminal Output: [5, 1, 3, 6, 7, 0, 2, 4]
  Expected Output: [5, 1, 3, 6, 0, 7, 2, 4]</p>
  
  <p>Here are the issues I am having. (1) The bfs doesn't take into account the order (priority) of courses that should be taken. Any suggestions on how to take into account the priority? (2) How do I figure out the start vertex for bfs? I can tell from drawing the graph but how can I tell from the input?</p>
  
  <p>Any suggestions would be appreciated</p>