As, BFS traverses level by level, so either v is at the same level (sibling) or v is at just the next level from u.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+17 votes

Consider an undirected unweighted graph $G$. Let a breadth-first traversal of $G$ be done starting from a node $r$. Let $d(r,u)$ and $d(r,v)$ be the lengths of the shortest paths from $r$ to $u$ and $v$ respectively in $G$. if $u$ visited before $v$ during the breadth-first traversal, which of the following statements is correct?

- $d(r,u) < d(r,v)$
- $d(r,u) > d(r,v)$
- $d(r,u) \leq d(r,v)$
- None of the above

+24 votes

Best answer

+1

@Arjun Sir

Plz chk this answer

First of BFS doesnot calculate according to shorest distance. After root we can take node any order. But if we take any parent first, it's children should be select first. So, u is first taken than doesnot mean u have shortest distance than v. But there is also a possibility that distance of (r,v) is less than distance of (r,u) . So, according to me d) will be answer.

Plz chk this answer

First of BFS doesnot calculate according to shorest distance. After root we can take node any order. But if we take any parent first, it's children should be select first. So, u is first taken than doesnot mean u have shortest distance than v. But there is also a possibility that distance of (r,v) is less than distance of (r,u) . So, according to me d) will be answer.

+2

@srestha, if we choose a node $x$ to visit in BFS then children of this node will not be visited until all the siblings of this node(which are at the same distance from root ) will be explored. henece if $u$ is visited first then only two cases are possible , either $u$ is nearest to root or $u$ is at the same distance as $v$ is.

+18 votes

Considering all given constraints :-

u is visited before q means 2-cases can only occur:-

Hence option C is Ans.

+1

Plz chk this answer

First of BFS doesnot calculate according to shorest distance. After root we can take node any order. But if we take any parent first, it's children should be select first. So, u is first taken than doesnot mean u have shortest distance than v. But there is also a possibility that distance of (r,v) is less than distance of (r,u) . So, according to me d) will be answer.

First of BFS doesnot calculate according to shorest distance. After root we can take node any order. But if we take any parent first, it's children should be select first. So, u is first taken than doesnot mean u have shortest distance than v. But there is also a possibility that distance of (r,v) is less than distance of (r,u) . So, according to me d) will be answer.

0

@shreshta as question is on BFS and we know that bfs works on unweighted graph..what you are saying is that vertex v can also have small distance but its not possible if distance would have been small than it would have been more closer to root..so according to bfs as its level order we need to go by that theory...vertex v can only have same distance as u or greater than v..in these two cases only vertex u can be visited before u..!

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 5k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.4k
- Admissions 412
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,942 questions

41,952 answers

119,194 comments

41,471 users