How to find bottleneck in directed graph

Question

Let's say we have a directed graph that represents school courses. Some courses are a prerequisite of others (e.g. [2,1] means that course 1 needs to be taken before course 2). We can take as many courses in parallel as we want, as long as the prerequisite is completed

I think this would naturally fit into a directed graph. To get the order of courses that can be taken, we would use topological sorting. If instead, we want to find the "bottleneck" course, what kind of algorithm makes sense?

A bottleneck looks like this:

• Lets say we have the following prerequisites: [2,1],[3,2],[6,3],[5,4],[6,5]
• That means we can take {1,4} in parallel, then {2,5}, then we have 3 as a "bottleneck" for course 6 because it's the last course that is left before we can take 6

Visualization attached below in case it helps

I'm not sure where to start with this problem

Answer 1

You seem to be assuming that

1. Every course MUST be taken
2. Every course takes the same amount of time

Algorithm:

• LOOP R over nodes that have an in-degree of zero ( no dependencies )
  • DO a breadth first search from R
    • WHEN search visits V
      • IF V never before visited, mark with distance from R
      • IF V previously visited, mark with larger of distance from R and previous mark
• LOOP over nodes with out-degree zero, keep track of node with largest mark
• LOOP over parents of node with largest mark
  • BOTTLENECK is parent with largest mark.

Answer 2

1. Start from the root node.
2. Find the child node having the largest height.

This can be done if you store the children in an array of pointers( in a binary tree we will have pointers to the left child and right child. In general, if we store the children in an array of pointers(for e.g. child[0] refers to the leftmost child.....child[n-1] for the nth child from left.)

3. The child node having the largest height will automatically be the bottleneck.