Register

GATE CSE 2014 | Set 2 | Question: 14

• edited by
18,426 views
65 65 votes

Consider the tree arcs of a BFS traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ formed by the tree arcs is a data structure for computing

  1. the shortest path between every pair of vertices.
  2. the shortest path from $W$ to every vertex in the graph.
  3. the shortest paths from $W$ to only those nodes that are leaves of $T$.
  4. the longest path in the graph.

9 Answers

Best answer
83 83 votes
BFS always has a starting node. It does not calculate shortest path between every pair but it computes shortest path between $W$ and any other vertex.

Correct Answer: $B$
• edited by
15 15 votes

BFS always produces shortest path from source to all other vertices in an unweighted graph.

So - B

3 3 votes

  • Option 1: "The shortest path between every pair of vertices."

    • Incorrect. BFS from a single source does not compute the shortest paths between every pair of vertices; that would require an all-pairs shortest path algorithm like Floyd-Warshall or repeated BFS/DFS for all nodes.

  • Option 2: "The shortest path from W to every vertex in the graph."

    • Correct. BFS ensures that the tree T contains the shortest path from W to every other vertex in an unweighted graph.

  • Option 3: "The shortest paths from W to only those nodes that are leaves of T."

    • Incorrect. BFS computes the shortest paths to all vertices, not just the leaves of the BFS tree.

  • Option 4: "The longest path in the graph."

    • Incorrect. BFS does not compute the longest path. Finding the longest path in a graph is a harder problem (NP-hard for general graphs).
2 2 votes
Don't get confuse here between Prims algorithm and BFS.

We don't have any concern of edge weights in BFS. In prims algo we take edge weights in consideration.

So, if we traverse a graph using BFS we will get the shortest path from "Source" to every vertex in the graph.(here source is W).

Here path means no of edges.

Correct me if I'm wrong.
0 0 votes

Here we can use the concept that

Idealogy of Dijkstra = BFS = PRIM'S

And Dijkstra's algorithm is a Greedy Algorithm to compute shortest path from single node to all the other nodes. 

Hence, Answer is B. 

Page:
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2014 | Set ...Next → · GATE CSE 2014 | Set ...
← Previous in category · GATE CSE 2014 | Set ...Next in category → · GATE CSE 2014 | Set ...
Position:
Show:

Related questions

62 62 votes
5 answers 5 answers
32.5k
32.5k views
go_editor asked Sep 28, 2014
32,458 views
GATE CSE 2014 | Set 3 | Question: 13
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checkin...
50 50 votes
5 answers 5 answers
19.3k
19.3k views
go_editor asked Sep 26, 2014
19,290 views
GATE CSE 2014 | Set 1 | Question: 11
Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$, when $G$ is represented as an adjac...
48 48 votes
9 answers 9 answers
21.9k
21.9k views
Kathleen asked Sep 14, 2014
21,882 views
GATE CSE 2001 | Question: 2.14
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 short...
93 93 votes
17 answers 17 answers
29.2k
29.2k views
Ishrat Jahan asked Nov 3, 2014
29,247 views
GATE IT 2005 | Question: 14
In a depth-first traversal of a graph $G$ with $n$ vertices, $k$ edges are marked as tree edges. The number of connected components in $G$ is$k$$k+1$$n-k-1$$n-k$