DFS Classification of Edges

DFS Classification of Edges

Introduction

DFS can do more than just mark reachable vertices. While DFS is moving through a graph, it creates a structure: some edges are used to discover new vertices, and some edges point to vertices that DFS has already seen. If we store the time when each vertex is entered and exited, we can understand what every edge means.

This idea is called classification of graph edges. It is especially useful in directed graphs, because different edge types tell us different things about the graph. For example, a back edge tells us that there is a directed cycle.

Problem or motivation

We are given a directed graph with $n$ vertices and $m$ directed edges. We run DFS over the whole graph. For every input edge $(x, y)$, we want to print its type:

• tree — DFS used this edge to visit $y$ for the first time.
• back — the edge goes from a vertex to one of its ancestors in the current DFS recursion.
• forward — the edge goes from a vertex to one of its descendants, but it was not the edge that discovered that descendant.
• — the edge goes to a vertex from another already finished part of the DFS forest.