[Data Structure] 그래프 깊이 우선 탐색(DFS, depth first search) 및 너비 우선 탐색(BFS, breath first search)

---

탐색

 

그래프의 어떤 정점에서 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것을 말한다. 효율적인 구간을 찾거나, 특정 정점에 도달 가능한지 알아볼 때 자주 사용된다.

탐색은 대표적으로 깊이 우선 탐색과 너비 우선 탐색이 존재한다. 말 그대로 깊이를 먼저 탐색하면 깊이 우선 탐색이고, 너비를 우선 탐색하면 너비 우선 탐색이다. 트리에서 전위, 중위, 후위 순환이 깊이 우선 탐색의 일종이고, 레벨 순회가 너비 우선 탐색의 일종이다.

 

---

DFS

 

한 방향으로 탐색 가능한 곳까지 가다가 더 이상 갈 수 있는 정점이 없다면 다시 가장 가까운 갈림길로 돌아와 그 갈림길부터 다시 안 간 방향으로 탐색을 진행하는 것을 말한다. 되돌아가기 위해 스택이 필요한데, 재귀를 이용하여 묵시적 스택 이용이 가능하다.

위 그래프에서 빨간색 노드를 시작으로 깊이 우선 탐색할 시 아래와 같이 탐색한다.

보는 기준으로 왼쪽 노드부터 탐색한다고 가정하였을 때 빨간색 실선을 따라 탐색하다가 더 이상 탐색할 곳이 없으면 빨간색 점선과 같이 뒤로 돌아간다. 숫자는 그래프가 탐색되는 순서이다.

C 를 이용하여 인접행렬로 표현되어 있는 그래프의 DFS를 구현하면 다음과 같다.

void DFS_mat(Graph* g, int v) {
    visited[v] = 1;
    printf("vertex %d -> ", v);
    for (int w = 0; w < g->n; w++) {
        if (g->adj_mat[v][w] && !visited[w]) {
            DFS_mat(g, w);
        }
    }
}

참고로 visited 배열을 따로 외부에 구현하고 싶지 않다면 아래와 같은 코드를 이용할 수 있다.

void DFS_recursive(Graph* g, int v, int* visited) {
    visited[v] = 1;
    printf("vertex %d -> ", v);
    for (int w = 0; w < g->n; w++) {
        if (g->adj_mat[v][w] && !visited[w]) {
            DFS_recursive(g, w, visited);
        }
    }
}

void DFS_mat(Graph* g, int v) {
    int* visited = (int*)malloc(sizeof(int)*g->n);
    for (int i = 0; i < g->n; i++) {
        visited[i] = 0;
    }
    DFS_recursive(g, v, visited);
    free(visited);
}

인접 리스트로 표현되어 있는 그래프의 DFS를 구현하면 다음과 같다.

void DFS_list(Graph* g, int v) {
    visited[v] = 1;
    printf("vertex %d -> ", v);
    for (Node* w = g->adj_list[v]; w; w = w->link) {
        if (!visited[w->vertex]) {
            dfs_list(g, w->vertex);
        }
    }
}

역시 따로 외부에 visited 배열을 구현하고 싶지 않다면 아래와 같은 코드를 사용할 수 있다.

void DFS_recursive(Graph* g, int v, int* visited) {
    visited[v] = 1;
    printf("vertex %d -> ", v);
    for (Node* w = g->adj_list[v]; w; w = w->next) {
        if (!visited[w->vertex]) {
            DFS_recursive(g, w->vertex, visited);
        }
    }
}

void DFS_list(Graph* g, int v) {
    int* visited = (int*)malloc(sizeof(int) * g->n);
    for (int i = 0; i < g->n; i++) {
        visited[i] = 0;
    }

    DFS_recursive(g, v, visited);
    free(visited);
}

DFS의 시간복잡도의 경우 인접행렬인 경우 $ \mathcal{O} (n^2) $ 이고, 인접 리스트의 경우 $ \mathcal{O} (n+e) $ 이다.

 

---

BFS

 

시작 정점부터 가까운 정점을 먼저 방문하고 가장 많이 떨어져 있는 정점을 가장 늦게 방문하는 방식으로 탐색을 진행하는 것을 말한다. 큐를 사용하여 구현된다.

위 그래프에서 빨간색 노드를 시작으로 너비 우선 탐색할 시 아래와 같이 탐색하는데, 먼저 보기 편하도록 탐색 시작 노드에서 각 노드가 얼마나 떨어져 있는지를 트리처럼 표현하면 아래와 같다.

탐색을 진행하면 아래와 같다.

보는 기준으로 왼쪽 노드부터 탐색한다고 가정하였을 때 빨간색 실선을 따라 탐색한다. 숫자는 그래프가 탐색되는 순서이다. 큐를 이용하기 때문에 다시 뒤로 돌아가지 않는다.

C 를 이용하여 인접행렬로 표현되어 있는 그래프의 BFS를 구현하면 다음과 같다. (큐에 대한 함수)

void BFS_mat(Graph* g, int v) {
    int w;
    Queue q;
    init_queue(&q);
    int* visited = (int*)malloc(sizeof(int)*g->n);
    for (int i = 0; i < g->n; i++) {
        visited[i] = 0;
    }
    visited[v] = 1;
    printf("%d visited -> ", v);
    enqueue(&q, v);
    while (!is_empty(&q)) {
        v = dequeue(&q);
        for (w = 0; w<g->n; w++) {
            if (g->adj_mat[v][w] && !visited[w]) {
                visited[w] = 1;
                printf("%d visited -> ", w);
                enqueue(&q, w);
            }
        }
    }
    free(visited);
}

인접 리스트로 표현되어 있는 그래프의 BFS를 구현하면 다음과 같다.

void BFS_list(Graph* g, int v) {
    Node* w;
    Queue q;
    init_queue(&q);
    int* visited = (int*)malloc(sizeof(int)*g->n);
    for (int i = 0; i < g->n; i++) {
        visited[i] = 0;
    }
    visited[v] = 1;
    printf("%d visited -> ", v);
    enqueue(&q, v);
    while (!is_empty(&q)) {
        v = dequeue(&q);
        for (w = g->adj_list[v]; w; w = w->next) {
            if (!visited[w->vertex]) {
                visited[w->vertex] = 1;
                printf("%d visited -> ", w->vertex);
                enqueue(&q, w->vertex);
            }
        }
    }
    free(visited);
}

BFS의 시간복잡도의 경우 인접행렬인 경우 $ \mathcal{O} (n^2) $ 이고, 인접 리스트의 경우 $ \mathcal{O} (n+e) $ 이다.