[알고리즘] 그래프 탐색(너비우선탐색(BFS), 깊이우선탐색(DFS))

그래프를 순회하는 방법에는 크게 BFS와 DFS가 있다.

1. 너비우선탐색 (BFS)

BFS는 시작 정점에서부터 출발하여 인접한 정점들부터 차례대로 방문하는 탐색 방법이다.

$L0$에서 시작하여 시작 노드와 가장 인접한 $L1$의 노드들을 차례대로 방문한다. $L1$의 노드들을 전부 방문했다면, 이젠 $L2$로 이동하여 노드들을 차례대로 방문한다.

이렇듯 그래프의 너비를 우선으로 탐색한다고 하여 Breadth-first algorithm이라고 한다.

소스코드

// 그래프 구조는 인접 행렬로 정의되어 있다고 가정한다.
void bfs(int start, int nodes) {
    queue[++rear] = start; // 시작 노드를 초기화하고 방문 표시
    visited[start] = true;

    while (front < rear) {
        int current = queue[++front]; 
        printf("%d ", current);

        for (int i = 0; i < nodes; i++) {
            if (graph[current][i] == 1 && !visited[i]) {
                // 현재 노드와 연결된 노드들 중 
                // 방문하지 않은 노드를 큐에 삽입하고 방문 표시
                queue[++rear] = i;
                visited[i] = true;
            }
        }
    }
}

인접 행렬로 구현시 최악의 경우 $O(n^2)$의 시간복잡도를 가질 수도 있으나, 인접 리스트로 구현할 경우에는 $O(n+m)$의 시간복잡도를 가질 수도 있다. 이때 $n$은 노드의 개수이고 $m$은 간선의 개수이다.

// 인접 리스트를 사용하는 BFS 함수, 이때 인접 리스트는 큐로 구현되어 있다.
void bfs(int startNode) {
    // 시작 노드를 큐에 삽입하고 방문 표시
    enqueue(startNode);
    visited[startNode] = true;

    while (front != rear) {
        int currentNode = dequeue();
        printf("%d ", currentNode); 

        // 현재 노드의 인접한 노드들을 순회하며
        // 방문하지 않은 노드를 큐에 삽입하고 방문 표시
        for (int i = 0; i < N; i++) {
            if (graph[currentNode][i] == 1 && !visited[i]) {
                enqueue(i);
                visited[i] = true;
            }
        }
    }
}

BFS로 탐색한 시작 노드로부터 리프 노드로까지의 경로는 최단 경로이다. 가중치가 없는 무방향 그래프에서 BFS탐색을 통해 최단 경로를 구할 수 있다.

---

2. 깊이우선탐색 (DFS)

DFS에서는 우선 시작 노드에서 인접한 노드 중 한 노드를 고르고, 그 노드의 리프노드까지 깊게 탐색한 후 다시 올라와 다음 인접한 노드를 방문하는 탐색 방법이다.

소스코드

void dfs(int node) {
    // 현재 노드 방문 표시
    visited[node] = true;

    printf("%d ", node);

    // 노드의 인접한 노드들에 대해 DFS를 호출한다.
    for (int i = 0; i < N; i++) {
        if (graph[node][i] == 1 && !visited[i]) {
            dfs(i);
        }
    }
}

인접한 노드 중 아직 방문되지 않은 노드가 존재하면 재귀호출하며, 더 이상 방문할 노드가 존재하지 않으면 뒤로 뒤돌아간다. 이때 시간복잡도는 $O(n+m)$이다.

DFS는 구현이 간단하고 속도가 빠른 편이다. 또 DFS를 이용하면 그래프에 사이클이 존재하는지 여부를 알 수 있다. 만약 DFS를 실행하여 한번 방문한 노드에 또 방문하게 된다면(백트래킹으로 돌아간 게 아닌 경우에) 그래프에는 사이클이 존재하는 것이다.

DFS는 무방향 연결 그래프를 탐색한다고 전제하고 있다. 만약 그래프가 연결된 그래프가 아니거나 방향이 존재한다면 DFS를 통해 모든 노드가 방문되지 않을 수 있다.

---

참고자료
그래프에서의 BFS / https://youtu.be/O7pDLEMsiBs
그래프에서의 DFS / https://youtu.be/ncR3yXlvyjE