CS 240: Lecture 38 – Graph Algorithms
I don’t know about you, but my mind has been elsewhere. Our routine striving was cut into by a break. I’m glad it did. Sometimes I think that I’ll only have peace when I get all the things done. What a lie that is. I will never be done. And even if something I’m working on gets finished, I won’t have peace afterward, not for long anyway. It’s better that breaks just interrupt us without waiting for a convenient time.
We pick up our conversation of algorithms and data structures with a couple of tricks for finding meaningful paths through graphs. First we’ll find a path that navigates through a prerequisite chain. Second we’ll find the shortest path from a vertex to another. These problems are pretty easy for humans to solve visually when the number of vertices is small. Don’t be deceived. As with every other topic in this class, we must assume that the size of our data structure will exceed our capacity to deal with it. Yet when we introduce the topic, we use small examples.
Imagine a series of tasks in a multi-task process. Some tasks must be completed before others. For example, maybe you’re planning a space flight. You’ve got to get some new o-rings before you assemble the solid rocket booster before you install the booster. Other tasks can be scheduled more freely, like celebrating a successful launch with a glass of Blue Powerade. They can happen any time after earlier stages. You can find a path through this process by making each stage a vertex. If a stage is a prerequisite for another, then there’s a directed and unweighted edge from the prerequisite to its successor. Then you run a topological sort on the graph.
The Greek word topos means place. The topological sort orders the vertices by their place in the prerequisite chain, not by any numeric value. The algorithm can be implemented a couple of different ways. We can run a depth-first traversal, chasing out the longest prerequisite chain in the graph and adding its vertices in backward order and branching recursively through the neighbors. A pseudocode implementation might look like this:
function topologicalSort(graph g) for each vertex v mark v as unvisited order =  for each vertex v if v is unvisited depthTraverse(g, v, order) function depthTraverse(graph g, vertex v, list order) mark v as visited for each neighbor n if n is unvisited depthTraverse(g, n) prepend v to order
Alternatively, if we wish to avoid the recursion, we can implement this with a breadth-first traversal. This implementation works by keeping a count of how many incoming edges each vertex has from unvisited vertices. When that number goes to 0, a vertex’s prerequisites have been visited and thus it is safe to visit the vertex. Here’s how it might be implemented in pseudocode:
function topologicalSort(graph g) create queue order =  for each vertex v inCounts[v] = 0 for each vertex v for each neighbor n increment inCounts[n] for each vertex v if inCounts[v] is 0 enqueue v while queue isn't empty v = dequeue append v to order for each neighbor n decrement inCounts[n] if inCounts[n] is 0 enqueue n
There are more legal topological sorts than these deterministic algorithms will generate. Consider this graph:
How many possible topological sorts are there for this graph? We’ll answer this as a peer instruction exercise.
The second algorithm we’ll look at today finds the quickest route from a starting vertex to all the other vertices in the graph. This algorithm was invented by Edsger Dijkstra, an opinionated computer scientist from the Netherlands. It works by maintaining a record of how distant each vertex is. Initially all vertices are infinitely far away, except for the starting vertex, which has a distance of 0. It advances to the next nearest vertex. If that vertex makes reaching other vertices cheaper, then those vertices’ distances are lowered. Then it advances again and again, until all vertices have been visited.
To actually trace out a path, the algorithm must keep track of which vertex provided the cheapest route. We walk this list of predecessors backward to generate the complete path.
function shortestPaths(graph g, vertex from, int distances, vertex predecessors) for each vertex v distances[v] = infinity predecessors[v] = null mark v as unvisited distances[from] = 0 repeat g.vertices.size v = find closest unvisited vertex mark v as visited if distances[v] is infinity return as there's no way to reach any more vertices for each neighbor n distanceViaV = distances[v] + g.weight(v, n) if distances[n] > distanceViaV distances[n] = distanceViaV predecessors[n] = v
To find the shortest path to a particular destination, we trace backward through the predecessors list, starting at the at destination and stopping at
For the remainder of our time, we will work through an exercise on Dijkstra’s algorithm.
You have some work to do before the next class:
- Keep working on PA4. It is due on Wednesday.
- Complete the quizzes by the end of today.
- Submit the lab by the end of today.
- There are no more OpenDSA readings.
See you next time.
P.S. It’s time for a haiku!
Course N won’t make sense
Not until course N + 1