그래프 (2) : 탐색의 방향?

그래프에서의 탐색은 우리가 일반적으로 알고 있는 자료구조에서 일반적으로 쓰이는 연산으로서의 의미 이외에도 여러 의미와 쓰임새를 가지고 있습니다.
이번 포스트에서는 그 의미와 쓰임새를 알아보고 탐색을 진행하는 방법에는 어떠한 것이 있는지 이야기해 보겠습니다.

---

1. 그래프에서의 탐색

그래프 용어에서 탐색은 몇가지 의미를 함축하고 있습니다.
단순한 의미로는 특정 정점(vertex)이 어디에 존재하는지 찾는 것입니다.
또 하나는 그래프 내에서 정점에 접근할 수 있을 때 그 정점과 연결된 또 다른 특정 정점을 찾는 것을 의미합니다.

경로(path)라는 용어는 그래프 용어로 한 정점에서 다른 정점으로 가는 간선들의 순열을 뜻합니다.

그래프의 탐색은 특정 정점 찾는 것 이외에도 두 정점이 서로 연결되어있는 상태인지 확인하는데도 쓰입니다.

 

---

 

2. 탐색 방법 (1) - 깊이 우선 탐색 ( Depth-First Search, DFS )

 

우선 깊이 우선 탐색 ( 이하 DFS )을 먼저 알아보겠습니다.

어떠한 그래프 탐색 알고리즘이든 핵심은 현재까지 방문한 정점을 기록해 두는 것입니다.

방문한 정점을 표시해 놓지 않으면 그래프는 Cycle을 가지기 때문에 무한으로 탐색이 진행될 수 있습니다.

 

이를 해결하는 방법은 정점을 키로 하는 해시 테이블의 사용입니다.
해시 테이블에 특정 키가 존재한다면 방문했다는 의미입니다.

 

DFS는 다음과 같이 동작합니다.

 

1. 그래프 내 임의의 점에서 시작
2. 현재 정점을 해시 테이블에 방문한 정점으로 추가
3. 현재 정점의 인접 정점 순회
4. 방문했던 인접 정점이면 무시
5. 방문하지 않은 정점이면 재귀적으로 깊이 우선 탐색 실행

 

이제 위 동작을 코드로 구현해 보겠습니다.

 

function dfs(vertex, searchValue, visitedVertices = new Map()) {
    // 현재 방문한 정점이 찾는 정점이라면 반환
    if (searchValue === vertex.data) return vertex
    // 방문 시 해시 테이블에 기록
    visitedVertices.set(vertex.data, true)
    for (const v of vertex.groupOfAdjacentVertices) {
        // 방문한 정점인 경우 건너띄기
        if (visitedVertices.has(v.data)) continue;
        // 현재 방문한 정점의 인접 정점이 찾던 정점이면 반환
        if (v.data === searchValue) return v;
        // 인접 정점에 대한 재귀 호출
        const foundVertex = dfs(v, searchValue, visitedVertices)
        if (foundVertex !== null) return foundVertex
    }
    // 찾는 정점을 찾지 못한 경우
    return null
}

 

---

 

3. 탐색 방법 (2) - 너비 우선 탐색 ( Breadth-First Search, BFS)

 

DFS와 달리 BFS는 재귀를 사용하지 않습니다.
대신 큐(Queue) 자료구조를 사용합니다.

 

BFS는 다음과 같이 동작합니다.

1. 그래프 내 임의의 점에서 시작 - 시작 정점
2. 시작 정점을 해시 테이블에 추가하여 방문 표기
3. 시작 정점을 큐에 추가 
4. 큐가 빌 때까지 실행하는 루프 시작
5. 루프 안에서 큐의 첫 번째 정점 삭제 후 현재 정점으로 지정
6. 현재 정점의 인접 정점을 순회
7. 이미 방문한 정점이면 무시
8. 방문하지 않은 정점이면 해시 테이블에 추가 후 큐에 추가
9. 큐가 빌 때까지 4 ~ 8 반복

 

이제 위 동작을 코드로 구현해 보겠습니다.

 

function bfs(startVertex) {
    // 방문 정점 기록 해시테이블
    const hashTable = new Map();
    // BFS Queue
    const queue = [];
    // 시작 정점 방문 기록
    hashTable.set(startVertex.data, true)
    // 시작 정점 BFS Queue enqueue
    queue.push(startVertex)
    // Queue가 빌 때까지 반복
    while (queue.length > 0) {
        const currentVertex = queue.shift()
        console.log(currentVertex.data)
        for (const v of currentVertex.groupOfAdjacentVertices) {
            // 방문하지 않은 정점이라면
            if (!hashTable.has(v.data)) {
                // 방문 기록
                hashTable.set(v.data, true)
                // BFS Queue Enqueue
                queue.push(v)
            }
        }
    }
}

 

---

 

4. DFS vs BFS

 두 탐색 방법은 그림으로 그려보면 다른 모양을 띕니다.

 

 

DFS가 탐색을 시작하면서 즉시 최대한 멀어진다면 BFS는 시작 정점 주변부터 시작하여 나선형을 그리며 점차적으로 멀어집니다.
그렇다면 어떠한 방법이 더 나은 탐색 방법일까요?
이는 상황마다 다릅니다.
예를 들어 주변 정점에 관계없이 멀리 떨어진 특정 대상을 찾는 문제라면 DFS가 유리할 것이고 정점과 직접 연결된 정점을 찾는 경우는 BFS가 유리하게 작동할 것입니다.
때문에 문제 상황에 맞는 선택을 필요로 합니다.

 

---

5. 그래프 탐색의 효율성

정점의 수를 $ V $,  간선의 수를 $ E $라고 했을 때 그래프 탐색의 시간 복잡도는 DFS, BFS 관계없이 $ O(V+2E) = O(V+E) $ 가 나오게 됩니다.