Java BFS와 DFS 구현

DFS

DFS는 깊이 우선 탐색으로, 한 노드에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 검색 속도 자체는 BFS에 비해 느리지만 조금 더 간단하다. 스택 혹은 재귀함수를 이용하여 구현한다.

class Graph{
    private int V;
    private LinkedList <Integer> adj[];

    Graph(int v){
        V = v;
        adj = new LinkedList[v];
        for(int i=0; i<v; i++){
            adj[i] = new LinkedList();
        }
    }

    void addEdge(int v, int w){
        // v번째 linkedList에 w 삽입
        adj[v].add(w);
    }

    void DFS(int v){
        boolean visited[] = new boolean[v];
        DFSUtil(v, visited);
    }

    void DFSUtil(int v, boolean visited[]){
        visited[v] = true;

        Iterator<Integer> it = adj[v].iterator();
        while(it.hasNext()){
            int n = it.next();
            if(!visited[n]){
                DFSUtil(n, visited);
            }
        }
    }
}

---

 

 

 

BFS

BFS는 너비 우선 탐색으로, 아래 그림과 같이 루트 노드에서 탐색을 시작하여 같은 레벨에 있는 노드를 모두 탐색한 다음 하위 레벨로 내려가 또 모두 탐색을 진행하다가, 더이상 탐색할 노드가 없을 때 탐색을 멈추는 방식으로 동작한다. 큐를 이용하여 구현한다.

class Graph{
    private int V;
    private LinkedList<Integer> adj[];

    Graph(int v){
        V = 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);
    }

    void BFS(int s){
        boolean visited[] = new boolean[V];
        LinkedList<Integer> queue = new LinkedList<Integer>();

        visited[s] = true;
        queue.add(s);

        while(queue.size() != 0){
            s= queue.poll();

            Iterator<Integer> i = adj[s].iterator();
            while (i.hasNext()){
                int n = i.next();
                if(!visited[n]){
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

---

 DFS, BFS를 활용하면 좋은 상황

DFS와 BFS를 활용하면 좋은 상황으로는 아래와 같은 상황들이 있다.

(1) 그래프의 모든 정점을 방문하는 것이 주요한 문제: DFS, BFS 모두 무방하다.

(2) 경로의 특징을 저장해둬야 하는 문제: 각 장점에 숫자가 있고 a 부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 하는 경우는 DFS를 사용해야 한다. BFS는 경로의 특징을 저장하지 못한다.

(3) 최단거리를 구하는 문제: BFS가 유리하다. DFS의 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만 BFS의 경우 먼저 찾아지는 해답이 곧 최단거리이기 때문이다.

 

 

 

 

 

Reference

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