Algorithms and Data Structures · Middle · Question 69 of 75
What is the "meet in the middle" idea in two-sided BFS?
- 1Start BFS from the vertex in the middle of the graph
- ✓Correct answer: Search from start and target at once until they meet
- 3Run BFS on half of the edges and DFS on the other half
Explanation
If each step branches b ways and the distance is d, one BFS explores about bᵈ states, two searches about 2 × b^(d/2). It's used in puzzles such as "word ladder".