BFS finds the shortest path from a source in an unweighted graph because
Ait visits vertices in order of edge distance
Bit uses a stack to explore deeply first
Cit sorts edges before traversing them
Dit relaxes edges V−1 times like Bellman-Ford
Answer & Solution
Correct answer: A. it visits vertices in order of edge distance
BFS expands a wavefront from the source, reaching all vertices at distance 1 before any at distance 2, and so on. The first time BFS reaches v is via the fewest edges, so that's the shortest path in unweighted graphs. Stack-based deep exploration is DFS; edge sorting is Kruskal; V−1 relaxations is Bellman-Ford.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for