Problem $5.$ Topological Sort $(10$ points$)$

$($a$)$ You are attending Breadmaker's University. To get your degree there are $7$ classes you must

take. There is some flexibility in the order you take them, but some of the classes have to

be taken before others because they are a prerequisite. Given the following table of class

prerequisites, determine an order you can take the classes while satisfying the requirements.

Solution:

co$-$op$.$ There may be several different courses you could start with to get there. Design an

algorithm that will determine which start class will have the fewest prerequisites in its path

to $"$F$"$ and print out an optimal ordering of classes. Here, optimal ordering means fewest

algorithm should take in a graph $G,$ and a destination node $v$ representing the target course.

You may:

Call the BFS algorithm we covered in class, posted on the course website

Assume that you can easily determine the in$-$degree and out$-$degree of every vertex

Solution: