If the sequence of vertices visited in a BFS structure of a graph is $G =…
2019
If the sequence of vertices visited in a BFS structure of a graph is $G = (V,E)$ is $ABCD$, then which of the following is correct?
- A.
G can be a complete graph
- B.
G can be a cycle
- C.
G can be a tree
- D.
All of the above
Attempted by 39 students.
Show answer & explanation
Correct answer: D
A BFS visit order of ABCD can occur in a complete graph, a cycle, or a tree depending on the start vertex and adjacency order. Therefore all listed graph types are possible.