Topological Sort

Topological sorting is a classic graph algorithm. Its purpose is to present a linear ordering of vertices composing a directed graph, in such a way that the directions of edges are respected.

Mathematically, a topological sort of a graph G is the ordering of vertices v1 v2 v3 ... vn such that for every edge directed from vi to vj, vi comes before vj in the ordering.

Consider the following directed graph. One possible topological sort would be 0, 1, 2, 3, 4. Another possible ordering is 0, 1, 2, 4, 3.

One practical application of topological sort could be, for example, to find the right order of classes to take as a CS/CSE major here at UC Davis. The classes would be the vertices, and edges would be drawn between classes if one is a pre-requisite of the other. By applying this algorithm, we would find out the right order to take classes!

We will implement this algorithm in its own class. Consider the following class along with its API:

Since topological sort is essentially a graph traversal, we must keep track of the vertices that have been visited. Also, since the algorithm only works for directed graphs, we should also keep track of in-degrees of every vertex. Add private data members and implement the following private helper functions:

Adapt the Breadth-First-Search (BFS) algorithm seen in lecture, in order to implement the topological sort algorithm. The two main modifications are:

The code is implemented as a private method that will be later called in the constructor. The prototype is as follows:

Now, implement the constructor of the TopologicalSort class. The constructor should take in a graph, fill in the in-degree of every vertex in G, and perform Topological sorting. Finally, implement public methods GetOrdering() and HasOrdering(). You may use Graph.h. Write your solution below.

Answer:

Your answers are saved to this Google doc.