Breadth first Search

Question

Which of following statement is true ?

A. In BFS of UDG there are no back edges and forward edges.

B. In BFS of Directed Graph there is no back edge and forward edges.

C. In BFS of UDG for each back edge(u,v) we have 0<= v.d <= u.d

D. Both b and c.

Ans. A

Comments

Well a back edge determines presence of cycle, its only in directed graph because when we say draw a BFS tree of a directed graph only tree edges will be included and now if we analyze the tree and the original graph, any back edge is a non tree edge is always from a node in higher depth to a node in smaller depth (In corresponding BFS tree).

But in case of UDG, we cant classify edges into forward or backward because no direction is involved.

Please tell me if  i am wrong.

---

But in case of UDG, we cant classify edges into forward or backward because no direction is involved.

yes, this is true 

---

@Shaik Masthan,

no this is not true. first of all there is no backward edge, there is back edge.

second, back edge and forward edge are not named because of their direction or something. if that would be so, then even DFT of UDG would not be having back or forward edges, but they do have.

back and forward edges are named based on their nature, if they are pointing to their ancestor or their descendent respectively.

---

@Na462 bro please dont post the solution. let us invade more on any points :p because u bring good quality of questions

---

@aambazinga,

Brother please elaborate your point a little :)

---

Can you explain a little that why then option A is correct ?

---

this is complicated for me to explain in my words, that is why i copy pasting the solution.

If we found a back edge, this means that there are two vertices, one a descendant of the other, but there is already a path from the ancestor to the child that doesn’t involve moving up the tree. This is a contradiction since the only children in the bfs tree are those that are a single edge away, which means there cannot be any other paths to that child because that would make it more than a single edge away. To see that there are no forward edges, We do a similar procedure. A forward edge would mean that from a given vertex we notice it has a child that has already been processed, but this cannot happen because all children are only one edge away, and for it to of already been processed, it would need to have gone through some other vertex first.

---

In bfs whether graph is directed or undirected back edges concept is not there since after popping the current vertex from queue then its adjacent vertices are explored however  in dfs no pop operation is there vertices would be there on stack only visited flag is there in dfs only in directed graph concept of back edges will come correct if I am wrong

---

@aambazinga,

Thanks Brother, got it what you want to convey. in one word it is

Due to all neighbors are already evolved at the same time there is no possible of front(back) edge possible.

---

@Kaluti,

In DFS OF UDG, back edge would be there. This is because, suppose you are processing a vertex ... Now it is possible that this vertex can point to a vertex which is still on the stack(i.e; the computation of that vertex is unfinished till now), and that vertex is turned out to be an ancestor of the currently visiting vertex. And this is what is termed as back edge.

This case can never occur in the BFS, because whenever the currently visiting vertex points to its ancestor u, u has been removed from the queue by then(i.e; fully visited), and since it has been fully visited, that edge would be termed as cross edge, not back edge.

---

@aambazinga,

brother, i make the conclusion for BFS not for DFS ( i didn't wrote it due to we are discussing on BFS only )

therefore, your comment and my comment is equivalent.

if there is no possible of front(back) edges, it doesn't mean there is no cross edge. there may be cross edges present.

---

@Shaik Masthan,
dude my mistake... Again updated. Apologies.

---

Can anyone show me the example pls

---

everyone's perspective is different for the solution . The explanation is messed up.please provide answers in simple language.

---

In BFS of UDG there can be no forward edges or back edges. There are only tree edges and cross edges.

---

Shaik Masthan AND aambazinga   PLEASE CHECK THIS ..THIS IS CORRECT ? I JUST SUMMARIZED IT  AND DONT KNOW REASONS OF THEM IF IT IS CORRECT PLEASE EXPLAIN REASONS ALSO.

---

Ashwani OK THANK U

---

@eyeamgj

How is there a back edge in DFS and not BFS for an undirected graph?

And How is there a cross edge in BFS and not in DFS in undirected graph?

---

@eyeamgj Look I would like to correct myself again.

According to the definition of forward edge. A non-tree edge (u, v) is a forward edge if v is a descendant of u in the DFS tree (everything after 'u' in the stack is a descendant of 'u'). Now if you look by the definition, you should find no objection in accepting that undirected graph DFS should have a forward edge too. But if you have a sneak at CLRS, they have clearly written that a dfs of undirected graph contains only tree edges and back edges.

So, if you go by the standard book, dfs of undirected graph shouldn't have a forward edge. ( So, your chart is correct).

Also, I think that there shouldn't be any concept of forward edge in undirected graph. Forward edge should only occur in directed graph.

---

Ashwani LET ME CHECK ONCE  ALL BECZ I GET CONFUSED  REGARDING EDGE CLASSIFICATIONS OF BFS 

---

https://gateoverflow.in/279686/data-structure-doubt?show=279829#c279829

---

What is difference between forward edge and tree edge I think both would be same so why can not be there forward edge in depth First search

---

https://gateoverflow.in/4774/dfs-cross-edges-forward-edge-and-back-edges

[[Good question

---

Questions may be asked...

https://gateoverflow.in/204104/gate2018-30

---

Thanks a lot,I was about to skip this video cause it's 20 minutes long.

---

@Verma Ashish

updated !

thanks @Prateek Raghuvanshi

---

@Prateek Raghuvanshi 

Thanks Brother all doubts is over by video 

---

The video is maybe removed now, if someone have this video or link of it please share.

---

Do you have this video? It is unavailabe now,