DFS와 BFS

그래프

DFS와 BFS를 설명하기 앞서 자료구조인 '그래프'를 이해해야 한다.

 

그래프란 단순히 노드와 그 노드를 연결하는 간선으로 이루어진 비선형 자료구조이다.

 

그래프

DFS

Depth-First Search , 깊이 우선 탐색으로 위 그래프 기준으로 설명을 해보도록 한다.

위 그래프를 DFS로 탐색을 하게 된다면 다음과 같은 순서를 가지게 될 것이다. DFS 구현의 주로 스택과 재귀함수를 사용하는데, 탐색 순서는 다음과 같다. 주로 재귀함수를 사용해서 보편적인 풀이를 이끌어 낸다.

1. 1번에서 2번, 3번, 4번을 순차적으로 탐색

2. 4번에서 더이상 찾을 순번이 없기 때문에 2번의 다른 노드인 5번을 탐색

3. 5번에서 더 이상 찾을 순번이 없기 떄문에 6번, 7번 순으로 탐색

Stack으로 구현

 

 

 

 

BFS

Breadth-First Search, 너비 우선 탐색으로 인접 노드를 시작하여 먼저 탐색하는 방법이다.

 

 

BFS는 1번 노드로부터 인접 노드를 순회하면서 노드를 넓게 탐색한다. 재귀호출을 사용하는 DFS와 달리 탐색할 정점이 저장되어야하므로 저장공간이 많이 사용되며 노드 수가 많다면 최악의 경우의 수가 만들어질 수 있다.

BFS는 주로 Queue로 구현이 가능하며, 큐로 구현한다. 순서는 다음과 같다.

1. 1번 노드를 큐에 넣는다.

2. 1번 노드에 인접한 2번과 3번을 넣고 1번은 방문하였으니 삭제

3.  2번과 3번이 인접한 4,5,6번을 for문으로 순차적으로 넣고 2번과 3번은 모두 방문하였으니 삭제

4. 4번과 인접한 7번을 넣고 모두 방문한 4번 삭제

5. 5,6,7번 순으로 순차적으로 탐색

구현

실제로 코드를 통해서 구현해보도록 하자. 백준에 BFS와 DFS 구현 문제가 있다.

 https://www.acmicpc.net/problem/1260 

1260번: DFS와 BFS

 

구현을 해보면서 개념과 비교해보도록 하자. 개념외에 추가되는 부분을 문제를 풀기위하여 간선의 관계를 행렬로 구현한점(1) , 또 방문한 노드를 boolean array로 표현한점 (2)이다.  

private boolean[] check;
private int[][] map;
int n;
int m;
int v;

//1260(DFS와 BFS), 2178(미로 탐색), 2606(바이러스), 2667(단지번호붙이기) 2644(촌수계산)
public void problem1260() throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");

    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());
    v = Integer.parseInt(st.nextToken());

    check = new boolean[n + 1];
    map = new int[n + 1][n + 1];

    for (int i = 0; i < m; i++) {
        st = new StringTokenizer(br.readLine(), " ");
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        map[a][b] = 1; //행렬 제시
        map[b][a] = 1;
    }

    dfs(v);
    System.out.println();
    check = new boolean[n + 1];
    bfs(v);
}

private void dfs(int target) {
    check[target] = true; //방문
    System.out.print(target + " ");
    for (int i = 1; i <= n; i++) {
        if (map[i][target] == 1 && check[i] == false) {
            dfs(i);
        }
    }
}

private void bfs(int target) {
    Queue<Integer> q = new LinkedList<>();
    q.offer(target);
    while (!q.isEmpty()) {
        int pullTarget = q.poll();
        check[pullTarget] = true;
        System.out.print(pullTarget + " ");
        for (int i = 1; i <= n; i++) {
            if (map[i][pullTarget] == 1 && check[i] == false && i != pullTarget) {
                q.offer(i);
                check[i] = true;
            }
        }
    }
}

결과값