Algorithms on Graphs: Simplifying DAGs with Topological Sort

Source and Sink Vertices

Before we start, we need to be familiar with some terms: source and sink vertices.

Source Vertex

A source vertex is simply a vertex where no edges point towards it. For example:

We’ll use green to highlight a source vertex

Sink Vertices

While source vertices have edges that only point outwards, sink vertices are the exact opposite. They’re vertices with edges that only flow into them.

Topological Sort

It’s important to note that topological sort (aka top sort) only works on DAGs and while it isn’t really categorized as a sorting algorithm like Merge Sort and Quick Sort, it does have some similarities with them.

From original DAG to Top Sorted DAG

What I really want to stress is that top sort simplifies our DAGs in such a way that we can better see the flow of the edges. This makes it easier to understand which vertices can reach which vertices.

What distinguishes top sort from the other sorting algorithms is that the ordering of the elements (vertices) can be different but only in such a way that it remains consistent to the flow of the edges. Let’s look this example:

Coding Top Sort

Our approach to top sort will utilize our understanding of source and sink vertices. The idea is that we’ll use Depth-First Search (DFS) to help us find our sinks. Upon finding our sinks, we’ll add them to the end of an array and continue this process until we fill up the entire array.

Since the neighbors of C have already been visited, then C is added to the next open spot in the array

Runtime Analysis

Since we’re just doing DFS on all the unvisited vertices, the runtime is O(V + E) and the space complexity is O(V).

Summary

  • Source vertices are any vertices with only outward edges. There can be many source vertices in a graph.
  • Sink vertices are vertices that only have inward edges. There can also be many sink vertices in a graph.
  • Topological sort (top sort) sorts vertices in an ordering such that the edges from the vertices flow in one direction.
  • Top sort simplifies the DAGs to show clearer relationships between vertices.
  • Top sort has a runtime of O(V +E ) and a space complexity of O(V).

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store