The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+7 votes

Let $T$ be a Depth First Tree of a undirected graph $G$. An array $P$ indexed by the 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 \in 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 $(C)$ – like language. Assume that the variables have been suitably declared.

Give a method for finding and printing the cycle formed if the edge $(u,v)$ of $G$ not in $T$ (i.e., $e \in 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 $(C)$ – like language. Assume that the variables have been suitably declared.

+10 votes

Best answer

Union-Find Algorithm can be used to find the cycle.

Ref: http://www.geeksforgeeks.org/union-find/

+4 votes

Union find can take 0(logn) but we need time complexity proportional to cycle length.Lets see how we can do this:-

When we add a edge u-v ,which is in G but not int T,then cycle will come for sure as we have n edges now for n vertices.Now,if we clearly observe then we can see there are two paths now between u and v.

One is earlier path and one is the new path (by adding edge u-v).Now if we can find the earlier path between u and v ,then that path is the cycle and it will be our answer.So how to do that?

We are given with P array which is having parent of each node.Just start from node v and then get its parent say y,now goto to node y in P and get its parent .Do this until we get the node u,and keep on printing all the nodes we access.So,tis is how we get the cycle formed by adding edge u-v in o(m) time,where m is length of cycle.

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

See the below example.I added 1-3 edges from G to T.And now start from 3 in P array and traverse till we find 1.

Note that mif the path goes from root,then we can do some modification here in constant time because if you try to get path that goes from root ,then when you reach root its parent is root only and progress cannot be made.

0

Just one small Note:

In the DFS tree T either u is the ancestor of v or v is the ancestor of u , because G has (u,v) edge.

We can find out whether u is the ancestor of v or v is the ancestor of u, by using start,finish times of u and v( if u.s<v.s<v.f<u.f then u is the ancestor of v, or else if v.s<u.s<u.s<u.f then v is the ancestor of u, where .s is start time and .f is finish time of any vertex during DFS traversal).

Now if u is the ancestor of v, then we can use the method you mentioned(Just start from node v and then get its parent say y,now go to to node y in P and get its parent .Do this until we get the node u,and keep on printing all the nodes we access.)

If v is ancestor of u then the same process we can use but this time start with u(Just start from node u and then get its parent say y,now go to to node y in P and get its parent .Do this until we get the node v,and keep on printing all the nodes we access.)

In the DFS tree T either u is the ancestor of v or v is the ancestor of u , because G has (u,v) edge.

We can find out whether u is the ancestor of v or v is the ancestor of u, by using start,finish times of u and v( if u.s<v.s<v.f<u.f then u is the ancestor of v, or else if v.s<u.s<u.s<u.f then v is the ancestor of u, where .s is start time and .f is finish time of any vertex during DFS traversal).

Now if u is the ancestor of v, then we can use the method you mentioned(Just start from node v and then get its parent say y,now go to to node y in P and get its parent .Do this until we get the node u,and keep on printing all the nodes we access.)

If v is ancestor of u then the same process we can use but this time start with u(Just start from node u and then get its parent say y,now go to to node y in P and get its parent .Do this until we get the node v,and keep on printing all the nodes we access.)

+2 votes

Here we can run DFS on the DFS tree, to detect whether there is a cycle in O(V+E) time

Since, in a tree of n vertices, we have n-1 edges, adding a cycle will create n edges.

So, there will exist a cycle of exactly n edges when we add one edge to T.

So, now time complexity of DFS becomes, O(V+V)=O(V) which will be proportional to the length of the cycle.

Now, consider an example where we have a graph and DFS produces DFS tree for it.

And DFS tree will be

Now suppose I add a edge between 1-3 in the graph and now my algorithm would be

(1)Initialize all vertices of T to white.

Start with say 1

(2) Mark this vertex 1 with GREY color.

Now, push 1 onto stack and move to it's neighbor in T

(3)If 1's neighbor has color white(undiscovered vertex), push it onto the stack, mark it grey and now discover 2's neighbors.

(4)Then, we move to 5(white), marked grey, pushed onto stack and neighbor of 5 i.e. 4(white) being examined.

(5)4 marked greyed and pushed onto the stack.

(6) No more neighbor for 4, mark 4 as black and pop off 4 from the stack.

(7)Discovered 3 as white neighbor of 5, mark it grey and now examine all neighbor of 3.

(8)Now because of new edge added in T, vertex 1 which is grey is discovered as the neighbour of 3 and 3 is also gray.

Means we have encountered a back edge!!.

Now, return all the vertices which are in the stack and those will be the vertices which make up a cycle.

Time complexity-O(V)

+2

WHITE: Vertex is not processed yet. Initially all vertices are WHITE.GRAY: Vertex is being processed (DFS for this vertex has started, but not finished which means that all descendants (ind DFS tree) of this vertex are not processed yet (or this vertex is in function call stack)BLACK: Vertex and all its descendants are processed. While doing DFS, if we encounter an edge from current vertex to a GRAY vertex, then this edge is back edge and hence there is a cycle

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,871 questions

47,531 answers

146,040 comments

62,297 users