GraphPathFinder.java

import java.util.*;

public class GraphPathChecker {
    public static boolean bfs(Map<String, List<String>> graph, String start, Set<String> targets) {
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        Set<String> found = new HashSet<>();

        queue.add(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            String node = queue.poll();
            if (targets.contains(node)) {
                found.add(node);
                if (found.equals(targets)) {
                    return true; // Stop early if all required nodes are found
                }
            }
            
            for (String neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }

        return false; // Not all required nodes were reachable
    }

    public static boolean checkPathWithUnorderedNodes(Map<String, List<String>> graph, List<String> requiredNodes) {
        if (requiredNodes.isEmpty()) return false;

        String start = requiredNodes.get(0); // Pick any node as the start
        Set<String> targets = new HashSet<>(requiredNodes);

        return bfs(graph, start, targets);
    }

    public static void main(String[] args) {
        // Example bidirectional graph
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("A", Arrays.asList("B", "C"));
        graph.put("B", Arrays.asList("A", "D", "E"));
        graph.put("C", Arrays.asList("A", "F"));
        graph.put("D", Arrays.asList("B"));
        graph.put("E", Arrays.asList("B", "F"));
        graph.put("F", Arrays.asList("C", "E"));

        // Example: The path must include these nodes in any order
        List<String> requiredNodes = Arrays.asList("A", "B", "E", "F");

        System.out.println(checkPathWithUnorderedNodes(graph, requiredNodes)); // Output: true
    }
}