In class we saw an algorithm for finding a topological sort of the vertices in a directed, acylic graph. The algorithm was based on finding v$.$indgree for each vertex in the graph, and it used an external list L$.$

Compute in$-$degree of each vertex and store the in$-$degree in v:indegree.

For all v in V $,$ if v:indegree $=0$ then add v to the list L$.$

Repeat until L is empty:

Remove a vertex u from L and place it at the end of T$.$

For all v in Adj $[$u$]$

v:indegree $=$ v:indegree $-1.$

if v:indegree $=0$

add v to L

Suppose we wish to update this algorithm in order to solve the following problem:

Let G be a directed, acyclic graph, where each vertex has a diculty rating, v$.$rate. The problem is to find a topological ordering of the vertices, one which prioritizes vertices of low rating before vertices of high rating. For example, if several orderings are possible, the goal is to prioritize vertices of lowest rating before those of higher rating, as long as it respects the topological sort.