CODEWITHSUNDEEP
algorithmgraph-algorithm
crackerplace
crackerplace

Reputation: 5475

Does the DFS algorithm differentiate between an ancestor and a parent while computing back edges?

Below is the general code for DFS with logic for marking back edges and tree edges. My doubt is that back edges from a vertex go back and point to an ancestor and those which point to the parent are not back edges (Lets assume undirected graph). In an undirected graph we have an edge back and forth between 2 vertices x and y. So after visiting x when I process y, y has x as an adjacent vertex but as it's already visited, the code will mark it as a back edge.

Am I right in saying that? Should we add any extra logic to avoid this in case my assumption is valid?

DFS(G)
for v in vertices[G] do
    color[v] = white    
    parent[v]= nil
    time = 0        

for v in vertices[G] do
    if color[v] = white then
    DFS-Visit(v)

Induce a depth-rst tree on a graph starting at v.

DFS-Visit(v)
    color[v]=gray
    time=time + 1
    discovery[v]=time
    for a in Adj[v] do
       if color[a] = white then
        parent[a] = v
        DFS-Visit(a)
        v->a is a tree edge
       elseif color[a] = grey then  
        v->a is a back edge
    color[v] = black
    time = time + 1

white means unexplored, gray means frontier, black means processed

Upvotes: 0

Views: 1063

Answers (1)

default locale
default locale

Reputation: 13456

Yes, this implementation determines frontier nodes only by color (visited, not visited) and, thus, doesn't separate parent and ancestor nodes. So, each edge in DFS search tree will be marked as back edge.

In order to separate tree and back edges you need to separate edges to parent and ancestor nodes. Simple way is to provide parent node as a parameter to DFS-Visit (p). For example: 

DFS-Visit(v, p)
 color[v]=gray
 time=time + 1
 discovery[v]=time
 for a in Adj[v] do
   if color[a] = white then
       parent[a] = v
       DFS-Visit(a,v)
       v->a is a tree edge
   elseif color[a] = grey and (a is not p) then
       v->a is a back edge
 color[v] = black 
 time = time + 1

UPDATE: I haven't noticed you already store parent nodes. So, there is no need to introduce parameter: 

DFS-Visit(v)
 color[v]=gray
 time=time + 1
 discovery[v]=time
 for a in Adj[v] do
   if color[a] = white then
       parent[a] = v
       DFS-Visit(a)
       v->a is a tree edge
   elseif color[a] = grey and (a is not parent[v]) then
       v->a is a back edge
 color[v] = black 
 time = time + 1

Upvotes: 0

Related Questions