DFS / BFS

DFS

특징 

1. 모든 정점을 방문하고자 할 때 사용됨.
2. 재귀(Recursion) 혹은 스택(Stack)을 이용하여 구현.
3. 무방향 그래프나 방향 그래프 모두에 적용.
4. 모든 경로를 탐색하기 때문에 경로의 길이가 길어질 경우에는 BFS에 비해 시간이 오래 걸릴 수 있음.
5. 어떤 경로가 있는지를 확인할 때 사용.

장점

1. 현재 경로 상의 노드들만 기억하면 되므로 메모리 사용량이 적음.
2. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 찾을 수 있음.

단점

1. 최단 경로를 보장하지 않음.
2. 무한 루프에 빠질 수 있음.
3. 그래프가 큰 경우에는 탐색 공간이 너무 커져서 메모리 문제가 발생할 수 있음.

import java.util.ArrayList;
import java.util.List;

public class Graph {
    private int V; // 그래프의 정점 개수
    private List<List<Integer>> adjList; // 인접 리스트

    public Graph(int vertices) {
        this.V = vertices;
        adjList = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    // 그래프에 간선 추가
    public void addEdge(int source, int destination) {
        adjList.get(source).add(destination);
    }

    // DFS 탐색 메서드
    public void dfs(int vertex, boolean[] visited) {
        visited[vertex] = true;
        System.out.print(vertex + " "); // 방문한 정점 출력

        // 현재 정점과 연결된 모든 정점을 탐색
        for (int neighbor : adjList.get(vertex)) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited); // 재귀적으로 이웃 정점을 탐색
            }
        }
    }

    // DFS 탐색 시작
    public void dfsStart(int start) {
        boolean[] visited = new boolean[V]; // 방문 여부를 저장하는 배열
        dfs(start, visited); // 시작 정점부터 DFS 탐색 시작
    }

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

        System.out.println("DFS 탐색 결과:");
        graph.dfsStart(0); // 정점 0에서 시작하여 DFS 탐색 시작
    }
}

 

BFS

특징

1. 가까운 정점부터 탐색해나가는 알고리즘 

2. 큐를 사용하여 구현  

1. 시작 정점을 큐에 넣음
2. 큐에서 정점을 하나 꺼내어 방문
3. 방문한 정점과 인접한 모든 정점들을 큐에 넣음
4. 큐가 빌 때까지 위 과정을 반복

장점

1. 시작 정점에서 목표 정점까지의 최단 경로를 찾을 수 있음 
2. 그래프의 모든 정점을 방문할 때 유용
3. 깊이가 같은 노드를 모두 방문한 후에 깊이를 증가시키기 때문에, 어떤 경로가 있는지를 확인할 때 사용

단점

1. DFS보다 많은 메모리를 사용 (큐를 사용하기 때문에)
2. BFS는 재귀적으로 구현할 수 없음.

import java.util.*;

public class Graph {
    private int V; // 그래프의 정점 개수
    private List<List<Integer>> adjList; // 인접 리스트

    public Graph(int vertices) {
        this.V = vertices;
        adjList = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    // 그래프에 간선 추가
    public void addEdge(int source, int destination) {
        adjList.get(source).add(destination);
    }

    // BFS 탐색 메서드
    public void bfs(int start) {
        boolean[] visited = new boolean[V]; // 방문 여부를 저장하는 배열
        Queue<Integer> queue = new LinkedList<>(); // BFS를 위한 큐

        visited[start] = true; // 시작 정점 방문 표시
        queue.offer(start); // 시작 정점을 큐에 삽입

        while (!queue.isEmpty()) {
            int vertex = queue.poll(); // 큐에서 정점을 하나 꺼냄
            System.out.print(vertex + " "); // 방문한 정점 출력

            // 현재 정점과 연결된 모든 정점을 탐색
            for (int neighbor : adjList.get(vertex)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true; // 방문한 정점 표시
                    queue.offer(neighbor); // 방문하지 않은 정점을 큐에 삽입
                }
            }
        }
    }

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

        System.out.println("BFS 탐색 결과:");
        graph.bfs(0); // 정점 0에서 시작하여 BFS 탐색 시작
    }
}