Classify directed edges relative to a depth-first search forest. Tree edges discover a new vertex; forward edges reach a proper descendant without being its discovery edge; back edges reach an active ancestor; cross edges connect completed branches or trees. Discovery and finish intervals are nested for ancestry. The classification depends on the chosen search order, not only on the graph.
A directed edge from a vertex to an active ancestor in its depth-first search. Together with the tree path from that ancestor it witnesses a directed cycle.
A directed edge to a proper descendant in the depth-first search forest that is not a tree edge. Its endpoints satisfy .

Ancestors (4)

  1. Depth-first search
  2. Algorithm
  3. Computer science
  4. Home

View article source

Discussion (0)

New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version