Question 11
Back to Exercise
What is the output of the following Java program?
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Map<String, List<String>> g = new HashMap<>();
String[][] edges = {{"A", "C"}, {"A", "B"}, {"C", "D"}, {"B", "E"}, {"D", "F"}};
for (String[] e : edges) g.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
List<String> order = new ArrayList<>();
Set<String> seen = new HashSet<>(Set.of("A"));
Deque<String> q = new ArrayDeque<>(List.of("A"));
while (!q.isEmpty()) {
String u = q.poll();
order.add(u);
for (String v : g.getOrDefault(u, List.of())) if (seen.add(v)) q.add(v);
}
System.out.println(order);
}
}
- A [A, C, B, D, E, F] Correct
- B [A, C, D, F, B, E]
- C [A, B, C, D, E, F]
- D [A, B, E, C, D, F]
Correct Answer: Option A
BFS visits A's neighbours in list order (C before B), then their neighbours: D (from C) before E (from B), then F.
Discussion & Comments 0
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!