그래프

/* ── 그래프 정의: 정점(Integer) → 인접 정점 목록(List) ──── */
public class Graph {
    private final Map<Integer, List<Integer>> adj = new HashMap<>();

    public void addVertex(int v) {
        adj.putIfAbsent(v, new ArrayList<>());
    }

    // 무방향 그래프: 간선 하나를 양쪽 정점 리스트에 모두 추가합니다.
    public void addEdge(int v1, int v2) {
        addVertex(v1);
        addVertex(v2);
        adj.get(v1).add(v2);
        adj.get(v2).add(v1);
    }

    public List<Integer> neighbors(int v) {
        return adj.getOrDefault(v, Collections.emptyList());
    }
}

/* ── BFS: 큐(Queue, FIFO)를 이용해 가까운 정점부터 방문 ──── */
public List<Integer> bfs(Graph graph, int start) {
    List<Integer> visitOrder = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();

    visited.add(start);            // 큐에 넣을 때 바로 방문 처리
    queue.offer(start);

    while (!queue.isEmpty()) {
        int cur = queue.poll();
        visitOrder.add(cur);          // 1. 방문 순서에 추가

        for (int next : graph.neighbors(cur)) {
            if (!visited.contains(next)) {
                visited.add(next);      // 2. 중복 삽입 방지를 위해 미리 방문 처리
                queue.offer(next);
            }
        }
    }
    return visitOrder;
}

/* ── DFS: 재귀 호출 스택(LIFO)을 이용해 깊이 먼저 탐색 ───── */
public void dfs(Graph graph, int cur, Set<Integer> visited, List<Integer> visitOrder) {
    visited.add(cur);              // 1. 진입 즉시 방문 처리 (호출 스택에 push)
    visitOrder.add(cur);

    for (int next : graph.neighbors(cur)) {
        if (!visited.contains(next)) {
            dfs(graph, next, visited, visitOrder);  // 2. 재귀 호출
        }
    }
}                                       // 3. 함수 종료 시 호출 스택에서 pop

/* ── 호출 예시 ──────────────────────────────────────────── */
List<Integer> result = new ArrayList<>();
dfs(graph, start, new HashSet<>(), result);

/* ── 반복적 DFS: 재귀 대신 명시적 스택(Deque) 사용 ──────── */
// 재귀 DFS의 StackOverflowError 위험을 피할 때 사용합니다.
public List<Integer> dfsIterative(Graph graph, int start) {
    List<Integer> visitOrder = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Deque<Integer> stack = new ArrayDeque<>();

    stack.push(start);

    while (!stack.isEmpty()) {
        int cur = stack.pop();
        if (visited.contains(cur)) continue;   // BFS와 달리 pop 시점에 중복 검사
        visited.add(cur);
        visitOrder.add(cur);

        for (int next : graph.neighbors(cur)) {
            if (!visited.contains(next)) stack.push(next);
        }
    }
    return visitOrder;
}