G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge…
2020
G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4, v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7}. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge ?
- A.
v2v4
- B.
v1v4
- C.
v4v5
- D.
v3v4
Attempted by 228 students.
Show answer & explanation
Correct answer: B
In BFS starting at v1, neighbors v2, v3, and v4 are discovered first.
Edges connecting the root to these unvisited neighbors become tree edges.
Thus, (v1, v4) is a tree edge.
A video solution is available for this question — log in and enroll to watch it.