MyQuestionIcon

1

You visited us 1 times! Enjoying our articles? Unlock Full Access!

Directions

Consider the ...

Question

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

A

The shortest path between every pair of vertices.

No worries! We‘ve got your back. Try BYJU‘S free classes today!

B

The shortest path from W to only those nodes that are leaves of T.

No worries! We‘ve got your back. Try BYJU‘S free classes today!

C

The shortest path from W to every vertex in the graph

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

D

The longest path in the graph.

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Open in App

Solution

The correct option is C The shortest path from W to every vertex in the graph
BFS traversal from W gives the shortest path from W to every other vertex in the graph.

Suggest Corrections

thumbs-up

0

Similar questions

Q. In an unweighted, undirected connected graph the shortest path from a node S to every other node is computed most efficiently in terms of time complexity by

Q. We define D-Tree(G) as the tree obtained by applying the DFS algorithm on a graph G.
Consider the following statements regarding the same.

S_{1}

: If G is an undirected graph, then every edge in D-Tree (G) is either a tree edge or a back edge.

S_{2}

: If G is a undirected graph, then every edge in D-Tree(G) is either a tree edge, or a cross edge.

Which of the above statements are true ?

Q. Consider a binary tree, where for every node P -

Q \leq 2

, where P represents number of nodes in left sub tree for node S and Q represents the number of nodes in right sub tree for node S for h > 0. The minimum number of nodes present in such a binary tree of height h = 4 will be

Q. Identify the correct statements about DFS traversal of graph.
(i) It can be used to determine whether a graph is cycle or not
(ii) It identifies the connected components of an undirected graph
(iii) Traverses a single path of the graph until it visits a node with no successor.

Q. A___is an acyclic digraph, which has the only node with in-degree 0, and other nodes have indegree I.

View More

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

Where to Go?

MATHEMATICS

Watch in App

explore_more_icon

Explore more

Standard IV Mathematics

Join BYJU'S Learning Program

CrossIcon