LearnFrenzy
Sign in Take a free test

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

DFS order with an explicit stack Answer, explanation & discussion

  • Output
  • Hard
  • 0 comments
  • Answer explained
  • Moderated community
Question 13 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<>();
        Deque<String> stack = new ArrayDeque<>();
        stack.push("A");
        while (!stack.isEmpty()) {
            String u = stack.pop();
            if (!seen.add(u)) continue;
            order.add(u);
            for (String v : g.getOrDefault(u, List.of())) stack.push(v);
        }
        System.out.println(order);
    }
}
  • A [A, C, B, D, E, F]
  • B [A, C, D, F, B, E]
  • C [A, B, C, D, E, F]
  • D [A, B, E, C, D, F] Correct
Correct Answer: Option D

C is pushed before B, so B is on top and explored first. Recursive DFS would give [A, C, D, F, B, E]; push neighbours in reverse to match it.

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