basecs
Published in

basecs

Spinning Around In Cycles With Directed Acyclic Graphs

Spinning around in cycles with directed acyclic graphs!

Edges, edges, everywhere

The DFS algorithm is helpful in identifying cycles, determining edges, and ordering vertices.
Edge classification in a graph, part 1
Edge classification in a graph, part 2
A graph, reimagined as connected (sub)trees

Since a graph doesn’t have one single root node, it doesn’t form a single tree. Rather, a graph could contain many small subtrees within it, each of which would become obvious as we walked through the paths of the graph. A graph is less of an individual tree data structure, and more of an interconnected forest, with small subtrees within it.

An undirected graph can only ever have tree edges or backward edges, part 1

An easy way to remember the rules of edge classification is this: an undirected graph can only have tree edges and back edges, but a directed graph could contain all four edge types.

An undirected graph can only ever have tree edges or backward edges, part 2

Round and round

Cyclic vs. acyclic graphs
A directed cyclic graph, with a self-loop

As it turns out, the reason that the depth-first search algorithm is particularly good at detecting cycles is because of the fact that it is efficient at finding backward edges.

Cycle detection and backward edges
We can use DFS to detect cycles in a graph.

If any node added to the stack has a reference to a node that is already within the stack, we can be sure that we have a cycle in this graph.

Directed acyclic graphs (DAGs)

Topological sorting

Topological sort: a defintion
Topological sort and its resulting topological order
Topological sort can only ever be applied to DAGs, or acyclic graphs.

A topological sort can only ever be applied to directed acyclic graphs, or DAGs. It is impossible to run a topological sort on a directed graph with a cycle, since it is unclear where the sort itself should start.

Topological sort in action!

Resources

  1. Graph Topological Sort Using Depth-First Search, Sesh Venugopal
  2. Depth-First Search (DFS), Topological Sort, MIT OpenCourseWare
  3. Topological Sorting — Graph Theory, NerdFirstTV
  4. Graph Traversals, Andrew Myers, Cornell University Department of Computer Science
  5. Depth-first Search, Professor Steven Skiena
  6. Topological Sort, Professor Trevor Brown

--

--

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