[그림1] bfs와 dfs의 탐색 순서

DFS(깊이 우선 탐색)

그래프 완전 탐색 기법 중 하나이다.
bfs, dfs 모두 노드라는 분기점과 그 노드 사이를 연결하는 그래프를 가지고 있다. 따라서 구현에서 기록해야하는 건 노드를 방문했는지, 노드는 어떤 그래프를 가지고 다른 노드와 연결되어 있는 지 확인. 이 두 가지를 기록해야 한다.

DFS는 (노드 선택 -> 정답인지 확인 -> 연결된 노드 선택) 이 과정을 반복하며 답을 구한다. 그러다 보니 재귀를 이용하게 되는 데 재귀가 깊어지면 공간 복잡도에서 불리해지므로 주의하는 게 좋다.

우선 구현을 위해 노드사이의 연결관계를 나타낸 2차원 배열 graph와 방문했는 지 확인을 위한 배열 visited를 구현한다.

그 후 시작점을 정하고 그 시작점은 방문했으니 visited 배열에 true 표시를 해준다. 그 후 반복문을 이용해 전체 노드수 만큼 확인을 해주되 선택한 노드가 아직 방문하지 않았고 전 노드와 연결이 된 경우만 확인을 해주며 재귀를 이용해 반복해준다.

void dfs(int idx) {
        System.out.print(idx + " ");
        visited[idx] = true;
        for (int i = 1; i <= N; i++) {
            if (!visited[i] && graph[idx][i]) {
                dfs(i);
            }
        }
    }

BFS(넓이 우선 탐색)

dfs와 달리 bfs는 선택 노드와 연결된 모든 노드를 확인하고 넘어가는 식으로 진행한다. dfs가 노드와 연결된 노드를 계속 반복하며 재귀적으로 짚고 넘어갔다면 bfs는 일단 시작점이 정답인지 확인하고 연결된 모든 노드를 LinkedList에 넣어준다. 그리고 리스트에 저장된 노드들을 하나씩 까면서 확인하고 연결된 노드들은 큐 뒤에 전부 집어 넣어준다. 이렇게 순서대로 큐 구조로 노드를 집어 넣어주니 노드 탐색이 마치 층층마다 [그림1]과 같이 확인한다.

구현은 역시 노드 연결을 기록한 배열과 graph와 확인여부를 판단할 배열 visited를 만들어서 기록해준다. 또한 확인한 노드와 연결된 노드를 큐 구조에 집어넣어준다. 큐 구조에 쌓인 노드들을 다 확인 할 때 까지 이를 반복 해주면 된다. 일반적으로 LinkedList가 삭제와 추가의 반복이 유리하기 때문에 구현에 많이 쓰인다. 아래에선 큐 구조로 구현하였다.

static void bfs(int idx) {
        queue = new ArrayList<>();
        visited = new boolean[1001];
        
        queue.add(idx); 
        visited[idx] = true;
        
        while(!queue.isEmpty()) {
            int curIdx = queue.remove(0);
            System.out.print(curIdx + " ");
            for (int i = 1; i <= N; i++) {
                if (!visited[i] && graph[curIdx][i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }