[알고리즘] DFS와 BFS JAVA

깊이 우선 탐색 DFS (Depth-First Search)

 

 

 

 

1. 시작 노드 선택: 탐색을 시작할 노드를 선택합니다.
2. 노드 방문: 현재 노드를 방문하고, 방문했다고 표시합니다.
3. 인접 노드 탐색: 현재 노드에 인접한 노드들 중 방문하지 않은 노드로 이동합니다.
4. 반복: 더 이상 방문할 노드가 없을 때까지 인접 노드로 이동하는 과정을 반복합니다. 모든 인접 노드를 방문했다면, 이전 노드로 돌아가서 다음 인접 노드를 탐색합니다.

 

DFS의 활용

• 미로 찾기: DFS는 미로 찾기와 같은 경로 탐색 문제에 유용합니다.
• 사이클 탐지: 그래프에서 사이클이 존재하는지 확인할 때 사용됩니다.
• 강결합 요소 찾기: DFS는 그래프에서 강결합 요소를 찾는 알고리즘의 기본이 됩니다.
• 위상 정렬: 유향 비순환 그래프(DAG)에서 위상 정렬을 수행할 때 DFS를 사용합니다.

 

장점

1. 메모리 효율성 : 현재 경로만을 기억하기 때문에, 대규모 그래프에서도 상대적으로 적은 메모리를 사용합니다.
2. 구현 용이성 : 재귀를 통해 간단하게 구현할 수 있으며, 코드가 직관적이고 이해하기 쉽습니다.
3. 부분 문제 해결 : 백트래킹 기법을 사용하는 문제(예: 퍼즐, 미로 탐색)에서 유용합니다.
4. 탐색 깊이 :목표 노드가 깊은 곳에 있을 때 효율적으로 찾을 수 있습니다.

단점

1. 무한 루프 가능성 : 순환 그래프에서 방문한 노드를 추적하지 않으면 무한 루프에 빠질 수 있습니다.
2. 불필요한 경로 탐색 : 불필요하게 깊은 경로까지 탐색할 수 있어, 최단 경로를 찾는 데 비효율적일 수 있습니다.
3. 스택 오버플로우 : 재귀 호출이 너무 깊어지면 스택 오버플로우가 발생할 수 있습니다.
4. 최단 경로 탐색의 부적합성 : DFS는 최단 경로를 보장하지 않으므로, 최단 경로를 찾는 문제에는 적합하지 않습니다.

 

구현

 

1. 정점 v 방문한다.
2. 정점 v에서 인접한 정점 중에 방문하지 않은 정점 w가 있다면 w를 v로 하여 1부터 반복한다(재귀함수 호출).
3. 인접한 정점 모두 방문했다면 스택에서 정점을 꺼내 위를 반복한다.

// 방문 여부를 저장하는 배열
static boolean[] visit;
// 그래프를 나타내는 연결 리스트 배열 또는 인접 행렬
static LinkedList<Integer>[] graph;
static int[][] adjMatrix;

// DFS 탐색 메서드
public static void dfs(int v) {
    visit[v] = true; // 현재 노드 v를 방문했음을 표시합니다.
    System.out.println(v); // 방문한 노드를 출력합니다.

    // 현재 노드 v와 인접한 모든 미방문 노드에 대해 재귀적으로 DFS를 호출합니다.
    for (int nextV : graph[v]) {
        if (!visit[nextV]) {
            dfs(nextV); // 방문하지 않은 인접 노드에 대해 DFS 호출
        }
    }
}

출력
1 2 4 6 5 3 

 

 

1. 재귀호출

import java.util.*;

class Graph {
    private LinkedList<Integer> adj[]; // 각 정점의 인접 리스트를 저장할 배열

    // 그래프 생성자: 정점의 수에 따라 인접 리스트 배열 초기화
    Graph(int v) {
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList(); // 각 정점에 대한 인접 리스트 초기화
    }

    // 그래프에 간선 추가 메서드
    void addEdge(int v, int w) {
        adj[v].add(w); // 정점 v에서 정점 w로 가는 간선 추가
    }

    // 재귀적으로 DFS를 수행하는 유틸리티 메서드
    void DFSUtil(int v, boolean visited[]) {
        visited[v] = true; // 현재 노드를 방문했음을 표시
        System.out.print(v + " "); // 방문한 노드를 출력

        // 현재 노드와 인접한 모든 미방문 노드에 대해 재귀적으로 DFSUtil 호출
        for (int n : adj[v]) {
            if (!visited[n])
                DFSUtil(n, visited); // 방문하지 않은 노드에 대해 재귀적으로 DFSUtil 호출
        }
    }

    // DFS 탐색을 시작하는 메서드
    void DFS(int v) {
        boolean visited[] = new boolean[adj.length]; // 방문 여부를 저장할 배열 초기화
        DFSUtil(v, visited); // DFSUtil 메서드 호출
    }

    // 메인 메서드
    public static void main(String args[]) {
        Graph g = new Graph(4); // 그래프 생성

        // 그래프에 간선 추가
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        // 시작 노드 2에서 DFS 탐색 시작
        System.out.println("Following is Depth First Traversal " +
                "(starting from vertex 2)");
        g.DFS(2); // DFS 탐색 시작
    }
}

2. 스택

import java.util.*;

class Graph {
    private LinkedList<Integer> adj[]; // 각 정점의 인접 리스트를 저장할 배열

    // 그래프 생성자: 정점의 수에 따라 인접 리스트 배열 초기화
    Graph(int v) {
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList(); // 각 정점에 대한 인접 리스트 초기화
    }

    // 그래프에 간선 추가 메서드
    void addEdge(int v, int w) {
        adj[v].add(w); // 정점 v에서 정점 w로 가는 간선 추가
    }

    // 스택을 이용한 DFS 탐색 메서드
    void DFS(int v) {
        boolean visited[] = new boolean[adj.length]; // 방문 여부를 저장할 배열 초기화
        Stack<Integer> stack = new Stack<>(); // 스택 생성
        stack.push(v); // 시작 노드를 스택에 push
        visited[v] = true; // 시작 노드를 방문했음을 표시

        // 스택이 빌 때까지 반복
        while (!stack.isEmpty()) {
            v = stack.pop(); // 스택에서 노드 하나를 pop하여 방문
            System.out.print(v + " "); // 방문한 노드 출력

            // 현재 노드의 인접한 노드들 중 방문하지 않은 노드를 스택에 push
            for (int n : adj[v]) {
                if (!visited[n]) {
                    visited[n] = true; // 인접 노드를 방문했음을 표시
                    stack.push(n); // 스택에 push
                }
            }
        }
    }

    // 메인 메서드
    public static void main(String args[]) {
        Graph g = new Graph(4); // 그래프 생성

        // 그래프에 간선 추가
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        // 시작 노드 2에서 스택을 이용한 DFS 탐색 시작
        System.out.println("Following is Depth First Traversal " +
                "(starting from vertex 2)");
        g.DFS(2); // DFS 탐색 시작
    }
}

 

 

 

너비우선 탐색 BFS (Breadth-First Search)

 

 

1. 시작 노드 선택: 탐색을 시작할 노드를 선택합니다.
2. 큐에 시작 노드 삽입: 시작 노드를 큐에 삽입하고 방문했다고 표시합니다.
3. 큐에서 노드 추출: 큐에서 노드를 하나 추출하여 방문합니다.
4. 인접 노드 큐에 삽입: 방문한 노드의 인접 노드들 중 방문하지 않은 노드를 큐에 삽입하고 방문했다고 표시합니다.
5. 반복: 큐가 빌 때까지 3-4번 과정을 반복합니다.

 

 

 

• 최단 경로: 무가중치 그래프에서 BFS는 최단 경로를 보장합니다.
• 메모리 사용량: 큐에 노드를 저장하기 때문에, 한 번에 많은 노드를 저장해야 할 경우 메모리 사용량이 많아질 수 있습니다.
• 넓이 우선 탐색: 각 레벨의 모든 노드를 탐색한 후 다음 레벨로 이동합니다.

 

 

 

BFS의 장단점

장점

1. 최단 경로 탐색: 무가중치 그래프에서 두 노드 간의 최단 경로를 찾을 수 있습니다.
2. 구현 용이성: 큐를 이용한 구현이 직관적이고 간단합니다.
3. 레벨 순 탐색: 특정 레벨까지의 모든 노드를 탐색할 수 있습니다.

단점

1. 메모리 사용량: 너비 우선 탐색은 큐에 많은 노드를 저장해야 할 수 있어 메모리 사용량이 많아질 수 있습니다.
2. 깊은 그래프에서 비효율적: 깊이가 깊은 그래프에서는 많은 노드를 방문해야 하므로 비효율적일 수 있습니다.

 

 

구현

1. 정점 v 방문한다.
2. 정점 v에 인접한 정점 중 방문하지 않은 정점을 차례로 방문하면서 큐에 넣는다.
3. 인접한 정점 모두 방문했다면 큐에서 dqueue하여 받은 값 정점 v로 설정하고 2를 반복한다.
4. 큐가 공백이라면 탐색 완료한 것이다.

// 방문 여부를 저장하는 배열
static boolean[] visit;
// 그래프를 나타내는 연결 리스트 배열 또는 인접 행렬
static LinkedList<Integer>[] graph;
static int[][] adjMatrix;

// BFS 탐색 메서드
public static void bfs(int v) {
    Queue<Integer> queue = new LinkedList<>(); // BFS를 위한 큐 생성
    queue.add(v); // 시작 정점 v를 큐에 넣기
    visit[v] = true; // 시작 정점 v를 방문했음을 표시

    while (!queue.isEmpty()) {
        int temp = queue.poll(); // 큐에서 하나의 노드를 꺼내어 방문
        System.out.println(temp); // 방문한 노드를 출력합니다.

        // 현재 노드 temp와 인접한 모든 미방문 노드들을 큐에 추가합니다.
        for (int nextV : graph[temp]) {
            if (!visit[nextV]) {
                queue.add(nextV); // 인접 노드를 큐에 추가
                visit[nextV] = true; // 인접 노드를 방문했음을 표시
            }
        }
    }
}

출력
1 2 3 4 5 6 

 

 

1. 큐를 이용한 구현

import java.util.*;

class Graph {
    private LinkedList<Integer> adj[]; // 각 정점의 인접 리스트를 저장할 배열

    // 그래프 생성자: 정점의 수에 따라 인접 리스트 배열 초기화
    Graph(int v) {
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList(); // 각 정점에 대한 인접 리스트 초기화
    }

    // 그래프에 간선 추가 메서드
    void addEdge(int v, int w) {
        adj[v].add(w); // 정점 v에서 정점 w로 가는 간선 추가
    }

    // BFS 탐색 메서드
    void BFS(int v) {
        boolean visited[] = new boolean[adj.length]; // 방문 여부를 저장할 배열 초기화
        LinkedList<Integer> queue = new LinkedList<>(); // 큐 생성

        visited[v] = true; // 시작 노드를 방문했음을 표시
        queue.add(v); // 시작 노드를 큐에 추가

        while (!queue.isEmpty()) {
            v = queue.poll(); // 큐에서 하나의 노드를 꺼내어 방문
            System.out.print(v + " "); // 방문한 노드 출력

            // 현재 노드의 인접한 모든 미방문 노드들을 큐에 추가
            for (int n : adj[v]) {
                if (!visited[n]) {
                    visited[n] = true; // 인접 노드를 방문했음을 표시
                    queue.add(n); // 큐에 추가
                }
            }
        }
    }

    // 메인 메서드
    public static void main(String args[]) {
        Graph g = new Graph(4); // 그래프 생성

        // 그래프에 간선 추가
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        // 시작 노드 2에서 BFS 탐색 시작
        System.out.println("Following is Breadth First Traversal " +
                "(starting from vertex 2)");
        g.BFS(2); // BFS 탐색 시작
    }
}

 

 

 

 

 

 

DFS 와 BFS 비교

 

 

비교 요약

DFS는 깊이 우선 탐색이므로 깊이를 우선으로 탐색합니다.

• 재귀적으로 구현할 수 있어 구현이 간단하고, 백트래킹에 유용하지만
• 최단 경로 탐색 등에는 적합하지 않을 수 있습니다.

BFS는 너비를 우선으로 탐색하여

• 최단 경로 문제에 유리하며, 네트워크 문제나 최적 경로 탐색에 적합합니다.
• 그러나 메모리 사용량이 많을 수 있고, 깊이가 깊은 경우에는 비효율적일 수 있습니다.

 

 

참고

https://scshim.tistory.com/241

[Algorithm] DFS와 BFS란? 작동 방식과 구현 방법(with 자바)

 

https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-BFS-DFS

https://velog.io/@smallcherry/Java-AlgorithmBFSAndDFS