1
$\begingroup$

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 its 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-first 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)<br>
            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'

$\endgroup$

2 Answers 2

3
$\begingroup$

The algorithm you describe works on directed graphs. In such a graph, an edge $(u, v)$ does not imply an edge $(v, u)$. Your confusion arises because you are probably trying it for undirected graphs.

For undirected graphs, the algorithm has to be modified slightly. Again, the modification will depend on whether this graph is a simple undirected graph or a multigraph. I will use the same variable names used that you use in your algorithm:

  • Simple Graph: When checking the colour of the adjacent vertex $a$ of a vertex $v$, if the colour is grey and the vertex $a$ is not a parent of $v$, then it is a back-edge. Ignore if $a$ is the parent.
  • Multigraph: If the colour of $a$ is grey and it is a parent of $v$, you need to check if $a$ occurs more than once in the adjacency list of $v$. This indicates multiple edges between $a$ and $v$, and one of them can be considered as a tree edge while the rest will be back edges. If there is only one edge between the two, it is a tree edge and has already been considered, so do nothing. Loops (edge from $v$ to $v$, that is, $a$ = $v$) are always back edges.

You are basically finding a spanning tree of the graph, and so try to go by the definitions and see how the algorithm should be modified for various cases. And how a tree-edge or a back edge are informally defined for various types of graphs.

$\endgroup$
1
  • $\begingroup$ Thanks.I wanted to clear my mind on that.Thanks for the info. $\endgroup$
    – whokares
    Dec 12, 2012 at 14:12
1
$\begingroup$

Usual definitions of back edge and tree edge is that they return to a node previously visited or that they go straight to a new node, respectively. Formally speaking, these definitions result from understanding graphs as spanning trees, so that my definitions are rather informal but I hope they suffice and are understandable.

Now, wrt the previous definitions, even if you are exploring an undirected graph, returning to the parent happens through a back edge since that node was already part of the current path ---and, of course, of the current spanning tree. Note that spanning trees are required to contain all nodes of the original graph, but usually a number of edges are removed.

Hope this helps,

$\endgroup$
4
  • $\begingroup$ Not sure if you got it right." returning to the parent happens through a back edge since that node was already part of the current path" ...Edges that go from a vertex to its parent are not back edges.That is my question.Only those edges that go from a vertex to an already visited ancestor are back edges. $\endgroup$
    – whokares
    Dec 12, 2012 at 7:59
  • $\begingroup$ A node $v$ that generates another node $a$ is an ancestor of $a$ and a depth-first traversal of the graph $G$ that contains these vertices would already list them in the spanning tree so, it is a back edge as far as I can say. $\endgroup$ Dec 12, 2012 at 8:23
  • $\begingroup$ What u said is true only for undirected graphs. $\endgroup$
    – whokares
    Dec 12, 2012 at 14:15
  • $\begingroup$ Certainly! I'm sorry I misunderstood your question then $\endgroup$ Dec 13, 2012 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.