Register

GO Classes 2024 | IIITH Mock Test 5 | Question: 32

• retagged by
250 views
1 votes
1 votes

Let $\text{G = (V, E)}$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in \text{V},$ let $d(x)$ denote the shortest distance in $\text{G}$ from $s$ to $x$. A breadth-first search (BFS) is performed starting at $s$.

Which of the following is/are ALWAYS true?

  1. There are no back edges
  2. There are no forward edges
  3. For each tree edge $(u, v)$, we have $d[v]=d[u]+1$
  4. For each cross edge $(u, v)$, we have $d[v]=d[u]+1$
• retagged by
User Avatar

1 Answer

2 votes
2 votes

We recommend you to first watch the following video to understand edges in BFS tree

This question is very much similar to the following PYQ-  https://gateoverflow.in/8321/gate-cse-2015-set-1-question-45

D is not correct because cross edge can be on the same level too.

For each cross edge $(u, v)$, we have $d[v]=d[u]+1$ or $d[v]=d[u]$.

• edited by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

337
views
1 answers
2 votes
GO Classes asked Apr 30, 2023
337 views
GO Classes 2024 | IIITH Mock Test 5 | Question: 23
Which of the following is/are TRUE?In the worst case, merge sort runs in $O\left(n^2\right)$ time.Depth-first search of a graph is asymptotically faster than ... a binary search tree leaves the same tree as inserting $y$ and then $x$.
User Avatar
294
views
1 answers
2 votes
GO Classes asked Apr 30, 2023
294 views
GO Classes 2024 | IIITH Mock Test 5 | Question: 31
Suppose we have a set of $n$ values. There are always at least one negative value and at least one positive value in the set.What is the worst case time ... known) and arranged in descending order then it takes $\theta(n)$ in worst case.
User Avatar
194
views
1 answers
1 votes
GO Classes asked Apr 30, 2023
194 views
GO Classes 2024 | IIITH Mock Test 5 | Question: 1
Let $\mathrm{R}(a, b, c, d)$ ... (r)$\prod_{a, c}(r)$\prod_{a, b}(r)$\prod_{a, b, d}(r)$
User Avatar
Link Copied!