MadeEasy Workbook: Algorithms - Graph Algorithms

Question

Comments

Is there are 3 cross edges??

---

.......

---

Answer 1

Starting from A : neighbors = B,D

Visit B: neighbors E

Visit E : neighbors C,G

Visit C : neighbors A,G

Visit G : neighbors null

backtrack till A

Visit D : neighbors F

Visit F.

now edges {FC, CA} forms loop hence back edges

edges {EG, FG } are cross edges.

Initially I've taken FC also as a cross edge but it helps to form a cycle hence it is not considered as a cross edge.

Comments

Yes Diksha is right EG is forward edge and FC and FG are cross edge.

---

FC and FG is cross edge......

cross edge:- (u,v) would be cross edge if  v is already visited and form u we could not reach to v or vice versa (in present DFS tree)

---

Okay I got my mistake thanks all.