DFS와 BFS를 비교해보자.

그래프의 탐색은 대표적으로 2가지로 나눌수 있다.

1) DFS(깊이 우선 탐색)

2) BFS(너비 우선 탐색)

두 종류 모두 모든 정점을 1번씩 방문한다는 목표가 있기는 하지만 방문하는 방법에 있어서 차이가 존재한다. 

먼저 DFS에 대해 알아보도록 하자.

 DFS의 경우에는 스텍을 이용하여 갈 수 있는 만큼 최대한 많이 가고, 갈 수 없으면 이전 정점으로 돌아가는 방식이다.

위에 그림을 통해 이해를 하자면 원래 스텍에 12345 이렇게 들어있다가 5에서 더이상 갈 곳이 없어서 5가 제거되고 6이 들어온 모습을 나타낸 것이다.

그렇게 4 3 2 1순으로 다시 계속 돌아오는 것이다.

보통 DFS의 경우에는 재귀호출을 통하여 구현한다. 코드를 간단하게 작성하자면 

void dfs(int x) {
        check[x] = true;
        printf("%d ",x);
        for (int i=1; i<=n; i++) {
            if (a[x][i] == 1 && check[i] == false) {
                dfs(i); }
        }
 }

이런식으로 쓸 수 있을것이다. dfs에 들어왔다는 것은 일단 그 정점을 방문했다는 것이므로 check[x] = true로 해주고, 그 지점에서 모든 정점을 탐색하면서 연결성이 있고, 방문된적이 없을경우 그 지점에서 다시 DFS를 하는 방식이다.

이번에는 BFS에 대해 알아보도록 하자.

BFS는 보통 큐로 구현을 한다. 큐를 이용하여 지금 위치에서 갈 수 있는 모든 지점을 큐에 넣는 방식으로 넣을때 방문했다고 체크를 해야한다.

위의 그림처럼 먼저 1을 체크하고 1과 연결된 2 5 를 체크한뒤 그 둘을 큐에 넣어주는 방식인것처럼 말이다.

먼저 인접행렬로 배열을 구현 하였을때 의 BFS의 구현코드를 살펴보도록 하자.

queue<int> q;
check[1] = true; q.push(1);
while (!q.empty()) {
    int x = q.front(); q.pop();
    printf("%d ",x);
    for (int i=1; i<=n; i++) {
        if (a[x][i] == 1 && check[i] == false) {
            check[i] = true;
            q.push(i); }
    }
}

먼저 1번부터 시작하기 때문에 check[1] = true로 해주고, 큐에 1을 넣는다. 그다음 큐가 빌때까지 가장 먼저 들어온 값이 다른 정점과 연결성이 있고, 그 정점이 방문된적이 없을경우 그 다른 정점을 true로 체크하고 그 배열을 큐에 넣어준다.

이번에 다루어본 방법들은 전부 인접행렬도 그래프가 구현되었을 경우에 대해 살펴보았는데 .... 인접리스트의 경우에는 나도 아직 확실하게 이해가 가지 않아서 .....

다음 시간에 다루어 보도록 하겠다.