in Algorithms recategorized by
2,638 views
12 votes
12 votes

In the graph shown above, the depth-first spanning tree edges are marked with a $’ T’$. Identify the forward, backward, and cross edges.

in Algorithms recategorized by
2.6k views

1 comment

To refer “Depth First Spanning Tree”

It is nothing but the Tree that is created by Traversing a DFS on a Graph.

Refer:

https://web.cs.wpi.edu/~kal/PLT/PLT8.6.5.html#:~:text=tree%20from%20the%20arcs%20of,a%20depth%2Dfirst%20spanning%20tree.
0
0

4 Answers

11 votes
11 votes
Best answer
  1. tree edge (T) is an edge in a DFS-tree.
  2. back edge (B) connects a vertex to an ancestor in a DFS-tree. (Includes a self-loop and this indicates the presence of a cycle)
  3. forward edge (F) is a non-tree edge that connects a vertex to a descendent in a DFS-tree.
  4. cross edge (C) is any other edge in graph $G.$ It either connects vertices in two different DFS tree or two vertices in the same DFS tree neither of which is the ancestor of the other.

For the given question,

  • Forward Edges: $1 \to 3, 2 \to 4$
  • Back Edges: $4 \to 5$
  • Cross Edges: $3 \to 7, 4 \to 6, 3\to 8, 4\to 8$

These are marked in the below graph. Below each node, its discovery time is marked. An edge $(u,v)$ becomes a forward edge only if $d(u) < d(v).$

PS:

  • An edge $(u, v)$ is a cross edge if and only if $d[v] < f[v] < d[u] < f[u].$ $(v$ is discovered and finished before $u$ is discovered$)$
  • An edge $(u, v)$ is a back edge if and only if $d[v] < d[u] < f[u] < f[v].$ $(v$ is discovered first and before it finishes $u$ is discovered and finished$)$

Reference: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

selected by
by

3 Comments

edited by

If the order of DFS traversal changes, will it affect the cross edges, back edges or forward edges??

means they will be different or remains same??

0
0
edited by

An edge (u,v) is a back edge if and only if d[v]<=d[u]<f[u]<=f[v].

Sir, above is the condition of Back Edge given in Cormen (with equality sign included), I am not able to make any case where discovery/finish time of U and V is equal, can you help me in understanding this? 

0
0

@manikantsharma

Consider a graph with single vertex and a self loop.

Initially, $d[0] = f[0] = 0$ and $vis[0] = false$

Assuming we use adjacency list, representation, we have $adj[0]$ = {$0$}

Now, begin $dfs(0)$ from this vertex,$vis[0] = true$ and $d[0] = 1$

Since $adj[0]$ has only $0$ and this vertex is already visited , we wont call dfs again

At the end of $dfs()$, we set $f[0] = 2$

Now, for $edge(0,0)$ , for condition $d[v] <=d[u] < f[u] <= f[v]$,

we get $d[0] <= d[0] < f[0] <= f[0]$ which evaluates to true. So, we have a back edge. 

0
0
0 votes
0 votes
FE- (2,4),(1,3),(3,8),(4,8)

BE-(4,5)

CE-(3,7),(4,6)

1 comment

(3,8), (4,8) are cross edges as their discovery and finishing times are of form {d[u],f[u]} {d[v],f[v]}
1
1
0 votes
0 votes
edge from ancestor to descendant-→ forward edge

edge from descendant to ancestor-→ backward edge

edge from neither ancestor nor descendant-→ cross edge
0 votes
0 votes

Just run the DFS on given graph and take those edges which marked as “T”.

now you will get this tree and in this tree make the remaining edges that were not marked as” T”.

After drawing those edges it is easily inferred,

Forward edge: Not a tree edge and it is from ancestor to descendant.

here it is 2->4 and 1 → 3

Backward edge: Not a tree edge and it is from descendant to ancestor.

here it is  4 → 5

Cross edge: edges between those vertices that don’t have a relation of ancestor and descendant.

here it is 4 → 6;  4 → 8; 3 → 7; 3 → 8

 

 

{ In diagram, F → Forward  B → Backward C → Cross} 

 

Related questions