LearnFrenzy
Sign in Take a free test

Data Structures in Java · Data Structures in Java Output Questions · Question 11

Order in which BFS visits a directed graph Answer, explanation & discussion

  • Output
  • Medium
  • 0 comments
  • Answer explained
  • Moderated community
Question 11 Back to Exercise

What is the output of the following Java program?

Main.java
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!

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links