datastructures11GraphImpl

1package pkg3datastructures;2 3/*4 * datastructures11GraphImpl.java5 * --------------6 * A graph stored as an adjacency list, with BFS and DFS traversals.7 * Supports directed or undirected edges.8 *9 * COMPLEXITY: BFS/DFS O(V + E). Adjacency list space O(V + E).10 * WHEN TO USE: networks, maps, dependencies, social graphs.11 */12import java.util.*;13 14public class datastructures11GraphImpl {15 16    private final Map<Integer, List<Integer>> adj = new HashMap<>();17    private final boolean directed;18 19    datastructures11GraphImpl(boolean directed) { this.directed = directed; }20 21    void addEdge(int u, int v) {22        adj.computeIfAbsent(u, k -> new ArrayList<>()).add(v);23        adj.computeIfAbsent(v, k -> new ArrayList<>());      // ensure v exists24        if (!directed) adj.get(v).add(u);25    }26 27    List<Integer> bfs(int start) {28        List<Integer> order = new ArrayList<>();29        Set<Integer> seen = new HashSet<>();30        Queue<Integer> q = new LinkedList<>();31        q.offer(start); seen.add(start);32        while (!q.isEmpty()) {33            int node = q.poll();34            order.add(node);35            for (int nb : adj.getOrDefault(node, List.of())) {36                if (seen.add(nb)) q.offer(nb);37            }38        }39        return order;40    }41 42    List<Integer> dfs(int start) {43        List<Integer> order = new ArrayList<>();44        dfs(start, new HashSet<>(), order);45        return order;46    }47    private void dfs(int node, Set<Integer> seen, List<Integer> order) {48        if (!seen.add(node)) return;49        order.add(node);50        for (int nb : adj.getOrDefault(node, List.of())) dfs(nb, seen, order);51    }52 53    public static void main(String[] args) {54        datastructures11GraphImpl g = new datastructures11GraphImpl(false);   // undirected55        g.addEdge(1, 2); g.addEdge(1, 3);56        g.addEdge(2, 4); g.addEdge(3, 4);57        g.addEdge(4, 5);58 59        System.out.println("BFS from 1: " + g.bfs(1));60        System.out.println("DFS from 1: " + g.dfs(1));61    }62}