We now will turn out attention to a few examples of graph algorithms that build on a basic depth-first or breadth-first search to solve a particular problem. As our first example, we will look at topological sorting.
Given a directed graph like the one below, a natural desire is to find a valid ordering for the verticies. If we are going to take one class at a time, what would be a valid order to take them in?
Taking a directed graph and producing a valid ordering of the vertices is called topological sorting. In the example above, one valid topological sort would be MTH111 -> MTH112 -> CS160 -> CS161 -> CS162 -> CS205. But that is not the only valid topological sort. CS160 does not depend on anything and nothing depends on MTH 112, so another valid topological sort would be CS160 -> MTH111 -> CS161 -> CS162 -> CS205 -> MTH112.
Finding a valid ordering for that simple graph is not too difficult. Some simple rules of thumb get us most of the way there. Anything with no prerequisites can be taken first. Anything that is not a prerequisite for anything else can be taken last. That leaves only a few things to sort out in the middle. But what if we had a much larger graph with many vertices and edges? The graph below is not much larger, but already much harder to sort at a glance.
We can do a topological sort by doing a series of depth-first searches until all vertices are visited. We will start from the first vertex and explore from there. When we finish a recursive call, we add the vertex to the front of a list of visited vertices.
If we are done with recursive calls in a depth-first search, we know that we have explored all vertices reachable from that vertex and they are already in the list. So it is safe to add the vertex to the front of the list at that point.
TopologicalSort(graph):
Set visitedSet
List topoSortOrder
for each vertex in graph:
if not visitedSet.contains(vertex):
// start a depth-first search from vertex
doTopoSort(graph, vertex, visitedSet, topoSortOrder)
doTopoSort(graph, vertex, visitedSet, topoSortOrder):
if visitedSet.contains(vertex):
return
visitedSet.add(vertex)
for each neighbor in graph.getNeighbors(vertex):
doTopoSort(graph, neighbor, visitedSet, topoSortOrder)
topoSortOrder.addFront(vertex)
If you compare doTopoSort with DFS from Listing 34.7.3, you’ll notice that the basic structure is the same. All we do is a little extra work to add items to the front of a list when we finish exploring them (line 15). Lines 4-7 make sure we visit every vertex in the graph by starting a depth-first search from each unvisited vertex.
The animation will load a random graph and start a depth-first search from vertex 0. Step through the animation. As you do so, watch how the TopoSortOrder table is updated.
The d label on each node shows the timestep we enter that vertex. The f label shows the timestep we finish exploring that vertex. When we finish exploring a vertex, we add it to the front of the TopoSortOrder list. Thus the final list is a reverse ordering of the finish times.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
