Let T be a Depth First Tree of a undirected graph G. An array P indexed by…

PYQ GATE 1992

Let T be a Depth First Tree of a undirected graph G. An array P indexed by vertices of G is given. P[V] is the parent of vertex V, in T. Parent of the root is the root itself.

Give a method for finding and printing the cycle formed if the edge (u,v) of G not in T (i.e., e ∈ G − T) is now added to T.

Time taken by your method must be proportional to the length of the cycle.

Describe the algorithm in a PASCAL - like language. Assume that the variables have been suitably declared.

Attempted by 2 students.

Sign up free to check your answer

Sign up free

Explore the full course: Data Structures

Loading lesson…