Skip to content

Instantly share code, notes, and snippets.

@skiadas

skiadas/topologicalSort.md

Created February 12, 2019 20:14
Show Gist options
  • Save skiadas/1e770dc7cf25b7772add89e6dac6600d to your computer and use it in GitHub Desktop.
Save skiadas/1e770dc7cf25b7772add89e6dac6600d to your computer and use it in GitHub Desktop.
Download ZIP
Topological Sort Notes
Raw
topologicalSort.md

Topological Sorting

  1. What is a directed acyclic graph?
  2. Example: CS major course prerequisites.
  3. What is a topological sorting for such a graph?

DFS solution to topological sorting

  1. How does DFS work in a directed graph? When will we encounter back-edges in this case?
  2. Perform DFS, noting the order in which vertices become dead-ends.
  3. The reverse of that order is a topological sort (WHY?).
  4. Example with our course requirement graph.
  5. Group activity: Do this for exercise 4.2.1a.

Decrease-by-one solution to topological sorting

  1. Record the incoming degree for each vertex (HOW?).
  2. Find a source vertex (incoming degree 0).
  3. Add it next on the ordering, and remove all edges emanating from it, adjust the numbers.
  4. If at any point there are no source vertices, then the graph is not acyclic.
  5. Example with our course requirement graph.
  6. Group activity: Do this for exercise 4.2.1a.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment