CODEWITHSUNDEEP
algorithmgraphdepth-first-search
mkzwm
mkzwm

Reputation: 495

Is DFS classification of edges valid?

DFS can be used to classify edges to tree, forward, back and cross.

Given the classification of edges and number of vertices, can we determine in linear complexity, is it a valid result of DFS? And if so - how?

For example, here is invalid classification: (it's impossible to get one like that, regardless of the root vertex we choose and the order of visiting children)

Upvotes: 3

Views: 421

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

Apologies for a somewhat brief answer: yes, and here's an algorithm. Verify that the tree edges indeed form a tree. For every other edge, compute the leafmost common ancestor of its endpoints. For forward edges, this should be the tail. For back edges, this should be the head. For cross edges, this should be neither.

Assuming that everything looks good so far, the rootward paths from the head and tail of a cross edge arrive at the LCA via different children. In every possible DFS order that generates the given classification, the head's child is visited before the tail's child. Collect all of these constraints and verify that there is no cycle.

I claim that, together, these checks are sound and complete. Completeness is verified by linearizing the constraints with a topological sort and constructing a plausible DFS order.

Upvotes: 2

Related Questions