DFS: Practice Exercise

Question

Q1. Consider the following DFS algorithm for cycle detection in a graph.

DFS(G)
    for each vertex u Belongs G.V
        u.color = WHITE
        U.pi = NIL
    time = 0
    for each vertex u Belongs G.V
        if u.color == WHITE 
            DFS-VISIT(G , u)
            
DFS-VISIT(G, u)
time = time + 1
u.d = time 
u.color = GRAY
for each v Belongs G.Adj[u]
    if (v.color == GRAY AND v.d + 1 < u.d)   // cycle detection Mechanism
        CYCLE DETECTED
    if(v.color == WHITE)
        v.pi = u
        DFS-VISIT( G, v)
u.color = BLACK
time = time + 1
u.f = time

Above Algorithm will detect the cycle in the graph - [True / False].

If your answer is false, then provide a counter case.

Q2. Cross edge can never be found in given Graph, but after getting DFS tree if we draw an edge from one leaf node to another leaf node then that edge is called cross edge.

Is this statement is true ??

Comments

1. I think true. As u.d is greater time taken than v.d. Means edge is going backward

2.is false. If cycle is found, then cross edge also possible there

---

But according to the definition of CLRS:-

Cross edges are all other edges. They can go between vertices in the same depth-first tree, as longs as one vertex is not an ancestor of the other, or they can go between vertices in different depth-first trees.

Answer 1

i think this code is not detect cycle between two vertices in a graph,

a---------------->b

a<-----------------b

because in this case v.d+1<u.d false

ans of second  we can find using cross edge plz visit  this link my this helps http://www.cs.yale.edu/homes/aspnes/pinewiki/DepthFirstSearch.html

Comments

Above algorithm will not detect the cycle in the Directed graph but it can detect in undirected graph.

ryt?

And what about 2nd statement

---

u should read this link material 4 case in which one case for cross edge  so second is false

---

no it  didn't in undirected  graph also this type of cycle possible