DFS: Edge classification

Dependencies:

  1. Properties of DFS

Let $G_π$ be the DFS forest obtained by performing DFS on $G$. The edges of $G$ can be partitioned into 4 classes:

  1. tree edges - $(u, v)$ is a tree edge iff $(u, v) \in G_π$.
  2. back edges - edges connecting a vertex to itself or to one of its ancestors in $G_π$.
  3. forward edges - edges connecting a vertex to one of its descendants in $G_π$.
  4. cross edges - the rest of the edges.

When $G$ is an undirected graph, we classify edges by running DFS on the directed version of $G$. If the classes of $(u, v)$ and $(v, u)$ are different, we choose the one which has more precedence. Precedence order, from highest to lowest: tree edge, back edge, forward edge, cross edge.

Dependency for:

  1. DFS: Online edge classification
  2. DFS: Reverse sorting by finish time gives topological ordering
  3. DFS: Edge classification in undirected graphs
  4. Directed graph is cyclic iff DFS gives back edges
  5. Undirected graph is cyclic iff DFS gives back edges

Info:

Transitive dependencies:

  1. /sets-and-relations/equivalence-classes
  2. /sets-and-relations/relation-composition-is-associative
  3. /sets-and-relations/equivalence-relation
  4. Graph
  5. Transpose of a graph
  6. Path in Graph
  7. Rooted tree
  8. Forest
  9. Properties of DFS