Question

which of the following statement is not true about breadth -first search (BFS) in an undirected graph starting at a vertex v?

a. BFS identifies all vertices reachable from v.

b. using an adjancey list instead of anadjancey matrix can improve the wrost case complexity to on (n+m).

c. BFS can't be used to check for a cycle in the graphs.

d. BFS can be used to identify the furthest vertex from V in any graph.
​

Answer 1

1. true
2. false
3. false
4. true

Explanation:

mark me as BRAINLIEST

Answer 2

(B) Using an adjacency list instead of an anadjancey matrix can improve the worst-case complexity to on (n+m)

BFS locates all vertices that can be reached from v. Using an adjacency list rather than an adjacency matrix reduces the worst-case complexity to on (n+m). BFS cannot be used to check the graphs for a cycle. In every graph, BFS may be used to find the vertex that is farthest from V. The only time you should use a BFS is if you know your (undirected) graph will have extensive paths and little path coverage (in other words, deep and narrow). In such a situation, BFS' queue would require far less memory than DFS' stack (both still linear of course).