Limited access

Upgrade to access all content for this subject

To graduate, your school is requiring you to take a certain set of classes. The 10 classes are displayed in the graph below as nodes where the edges in the graph represent the fact that the class is a prerequisite for the class that its edge points to.

Given the graph below and the fact that a student cannot take a class if they have not taken all of that class’s prerequisites first, which method would a student use to figure out what order to take their classes in while doing it as efficiently as possible?

Ashley Salzetti. Created for Copyright 2016. All rights reserved.


The student should enumerate each possible ordering and see if this ordering would allow the student to take all of their classes without taking any of a class’s prerequisite classes after the class they were required for.


The student should run Depth-First Search on each connected component of the above graph and use the ordering in which the algorithm finds the nodes as the order in which they should take the classes.


The student should find a class that has no prerequisites (no incoming edges) and place it first in the ordering. Then the student should remove the class and all of its outgoing edges from the group of remaining classes and edges. The student should continue doing this, placing each new class next in the ordering, until no classes are left.


The student should find a class that is not the prerequisite for any other class (no outgoing edges). Then the student should find the length of the shortest path from every class to that class. The order in which the student should take their classes is the descending order of path lengths, where the first class that was chosen is the last class in the ordering.

Select an assignment template