DFS BFS

DFS (Depth-First Search)

DFS는 그래프나 트리의 모든 노드를 방문하는 알고리즘 중 하나입니다. DFS는 재귀 또는 스택을 사용하여 구현

DFS의 예시 구현 (재귀)

import java.util.*;

public class DFS {
    private Map<Integer, List<Integer>> adjList = new HashMap<>();

    public void addEdge(int u, int v) {
        adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
    }

    public void dfs(int start) {
        Set<Integer> visited = new HashSet<>();
        dfsRecursive(start, visited);
    }

    private void dfsRecursive(int node, Set<Integer> visited) {
        visited.add(node);
        System.out.print(node + " ");

        for (int neighbor : adjList.getOrDefault(node, Collections.emptyList())) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {
        DFS graph = new DFS();
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        System.out.print("DFS starting from node 2: ");
        graph.dfs(2);
    }
}

BFS (Breadth-First Search)

BFS는 그래프나 트리의 모든 노드를 방문하는 또 다른 알고리즘입니다. BFS는 큐를 사용하여 구현

BFS의 예시 구현

import java.util.*;

public class BFS {
    public static void main(String[] args) {
        // 그래프를 2차원 배열로 표현해줍니다.
        // 배열의 인덱스를 노드와 매칭시켜서 사용하기 위해 인덱스 0은 아무것도 저장하지 않습니다.
        // 1번인덱스는 1번노드를 뜻하고 노드의 배열의 값은 연결된 노드들입니다.
        // 1번 노드는 2,3,8 과 연결되어있고 2번 노드는 1,6,8과 연결되어있다.
        int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};

        // 방문처리를 위한 boolean배열 선언
        boolean[] visited = new boolean[9];

        System.out.println(bfs(1, graph, visited));
        //출력 내용 : 1 -> 2 -> 3 -> 8 -> 6 -> 5 -> 4 -> 7 -> 
    }

    static String bfs(int start, int[][] graph, boolean[] visited) {
        //탐색 순서를 출력하기 위한 용도
        StringBuilder sb = new StringBuilder();
        //BFS 에 사용할 큐를 선언
        Queue<Integer> q = new LinkedList<Integer>();

        q.offer(start); // 큐에 BFS 를 시작할 노드 번호를 넣어준다
        visited[start] = true; // 시작 노드를 방문표시

        //큐가 빌때까지 반복
        while (!q.isEmpty()){
            int nodeIndex = q.poll();
            sb.append(nodeIndex+ "->");
            //큐에서 꺼낸 노드와 연결된 노드들 체크
            for (int i = 0; i < graph[nodeIndex].length; i++) {
                int temp = graph[nodeIndex][i];
                //방문하지 않았다면 방문처리후 큐에 넣기
                if (!visited[temp]) {
                    visited[temp] = true;
                    q.offer(temp);
                }
            }
        }
        return sb.toString();
    }
}

요약

• *DFS (Depth-First Search)**는 스택이나 재귀를 사용하여 그래프를 깊이 우선으로 탐색합니다.
• *BFS (Breadth-First Search)**는 큐를 사용하여 그래프를 너비 우선으로 탐색합니다.
• 방문 예정 노드를 푸시, pop 할때 방문처리 → dfs
• 지금 방문할 노드를 add() 그러므로 add하면서 방문처리 → bfs