CODEWITHSUNDEEP
c++algorithmgraphdepth-first-search
chotu123
chotu123

Reputation: 85

Depth first search tree edge classification

I've got a basic question about DFS edge classification: I have a directed graph with edges: 1->2, 2->3 and 1->3. The edge classification for 1->2 is tree edge, 2->3 is tree edge. I'm confused as to what the classification of 1->3 would be: forward edge, back edge or tree edge?

Upvotes: 0

Views: 1292

Answers (1)

GHC
GHC

Reputation: 2678

According to the definition of edge classification (see http://en.wikipedia.org/wiki/Depth-first_search for example), 1->3 would be a forward edge.

This would be because:
1->2: tree edge because 2 is a descendant of 1 and 2 has not yet been discovered.
2->3: tree edge because 3 is a descendant of 2 and 3 has not yet been discovered.
1->3: forward edge because 3 is a descendant of 1 and has already been discovered.

3 is a descendant of 1 both directly and via 2.

Upvotes: 1

Related Questions