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. Algorithms gate1989 descriptive algorithms graph-algorithms spanning-tree depth-first-search + – makhdoom ghaya asked Nov 30, 2016 recategorized Apr 16, 2021 by Lakshman Bhaiya makhdoom ghaya 2.7k views answer comment Share Follow See 1 comment See all 1 1 comment reply ShouvikSVK commented Dec 22, 2021 reply Follow Share 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 votes 0 votes Please log in or register to add a comment.
Best answer 11 votes 11 votes A tree edge (T) is an edge in a DFS-tree. A 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) A forward edge (F) is a non-tree edge that connects a vertex to a descendent in a DFS-tree. A 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 Arjun answered May 17, 2019 selected May 18, 2019 by akash.dinkar12 Arjun comment Share Follow See all 3 Comments See all 3 3 Comments reply Kiyoshi commented Nov 12, 2021 i edited by Kiyoshi Nov 12, 2021 reply Follow Share 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 votes 0 votes manikantsharma commented Sep 11, 2022 i edited by manikantsharma Sep 11, 2022 reply Follow Share 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 votes 0 votes sk91 commented Oct 12, 2022 reply Follow Share @manikantsharmaConsider 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 againAt 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 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes FE- (2,4),(1,3),(3,8),(4,8) BE-(4,5) CE-(3,7),(4,6) utk0203 answered Dec 24, 2016 utk0203 comment Share Follow See 1 comment See all 1 1 comment reply Ruchirchaitanya commented Oct 7, 2017 reply Follow Share (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 votes 1 votes Please log in or register to add a comment.
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 rangasthalam_ram answered Nov 17, 2023 rangasthalam_ram comment Share Follow See all 0 reply Please log in or register to add a comment.
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} GauravRajpurohit answered Jan 26 GauravRajpurohit comment Share Follow See all 0 reply Please log in or register to add a comment.