CODEWITHSUNDEEP
algorithmgraphdepth-first-search
andre_ss6
andre_ss6

Reputation: 1254

Does order of exploration in DFS affect edge classification

I'm implementing DFS and edge classification for college (based on the code provided in this paper: https://courses.csail.mit.edu/6.006/fall11/rec/rec14.pdf).

I've used this graph as a test:enter image description here

The letters in italic are simply the vertices' names, while the numbers inside the vertices are discovery and finalization time, respectively. Edges are classified as Back, Forward or Cross; all else are tree edges.

As you can see, this graph was visited in the following order: first s, then its neighbors (following DFS); when there were no more accessible neighbors, visitation began on t.

In order to test our algorithm, the teacher will provide a text file with each edge as a line. When performing the DFS, I simply follow the order of appearance in the file for each vertex; in this case, that would be first s and then v, not t. This in turn gives a different edge classification: t to v is considered a cross edge, t to u a back one and u to t a tree one.

Is this behavior normal? Does the order of exploration affect the final edge classification? If so, are both classifications, mine and the example's, correct? If not, is there any way I can know which vertex to explore first?

Upvotes: 3

Views: 923

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726849

Is this behavior normal? Does the order of exploration affect the final edge classification?

Absolutely. The order in which the algorithm chooses edges for exploration decides edge classification in cases when there are any back or cross edges (i.e. when the graph is not a tree.)

If so, are both classifications, mine and the example's, correct?

Yes, both classifications are correct, as long as there is no specific order of exploration requested by the problem setter.

If not, is there any way I can know which vertex to explore first?

The problem may specify a particular order of exploration - for example, the graph on your picture appears to be traversed in reverse alphabetical order of vertex naming: z before w from s, y before w from z, and v before u from t.

Upvotes: 2

Related Questions