[알고리즘] 너비 우선 탐색(BFS) / 깊이 우선 탐색(DFS)

반응형

 

그래프에서 탐색은 하나의 정점에서 시작해 모든 정점들을 한 번씩 방문하는 작업이다. 이에 대한 방법들이 바로 너비 우선 탐색과 깊이 우선 탐색이다.

 

자료구조에 대한 그래프는 여기로

[자료구조] 그래프

[자료구조] 그래프

 

너비 우선 탐색(Breadth First Search)

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 방법이다. 너비 우선 탐색은 큐를 이용한다. 정점들이 방문될 때마다 큐에 인접 정점을 삽입하고, 더 이상 방문할 인접 노드가 없다면 큐에서 꺼내고 꺼낸 정점의 인접한 정점들을 방문하게 된다. 아래 그림을 예시로 보자.

(a) A에서 시작한다. 큐에는 A가 저장되어있다. 큐 내용 : A
(b) A를 큐에서 꺼내고 B,C를 방문한다. 큐에 B,C를 삽입한다. 큐 내용 : BC
(c) B를 큐에서 꺼내고 D를 방문한다. 큐에 D를 삽입한다. 큐 내용 : CD
(d) C를 큐에서 꺼내고 E를 방문한다. 큐에 E를 삽입한다. 큐 내용 : DE
(e) D를 큐에서 꺼내고 F를 방문한다. 큐에 F를 삽입한다. 큐 내용 : EF
(f) E를 큐에서 꺼내고 G,H를 방문한다. 큐에 G,H를 삽입한다. 큐 내용 : FGH
(g) 더 이상 방문할 노드들이 존재하지 않는다. F, G, H를 각각 꺼낸다. 큐 내용 : 없음. 탐색 완료

 

1) 인접 행렬

// 인접 행렬
void BFS(int v) {
    queue<int> visit_q;
    visited[v] = true;

    visit_q.push(v); // 시작 정점을 큐에 저장

    while (!visit_q.empty()) { // 큐가 비어있지 않을 동안 반복
        v = visit_q.front(); // 큐에서 정점을 꺼낸다.
        cout << v << " ";
        visit_q.pop();

        for (int w = 0; w < vtxsize; w++) {
            if (grp[v][w] != 0 && visited[w] == false) { // 정점이 v랑 연결되어있고 방문되지 않았으면
                visited[w] = true; // 방문했다고 처리하고 큐에 저장
                visit_q.push(w);
            }
        }
    }
}

2) 인접 리스트

// 인접 리스트
void BFS(int v) {
    queue<int> visit_q;
    visited[v] = true;

    cout << vtx[v] << " ";
    visit_q.push(v); // 시작 지점을 큐에 저장

    while (!visit_q.empty()) { // 큐가 비어있지 않을 동안 반복
        v = visit_q.front(); // 큐에서 정점을 꺼낸다.
        visit_q.pop();

        for (GrpNode* w = grp[v]; w != NULL; w = w->link) {
            if (visited[w->id] != false) { // 정점이 방문되지 않았다면
                visited[w->id] = true; // 방문 처리
                cout << vtx[w->id] << " ";
                visit_q.push(w->id);
            }
        }
    }
}

너비 우선 탐색은 인접 행렬로 구현된 그래프면 \(\Theta(n^2)\)이, 인접 리스트로 구현된 그래프면 \(\Theta(n + e)\)의 시간이 걸린다.

깊이 우선 탐색(Depth First Search)

시작 정점에서부터 임의의 인접한 정점으로 탐색을 시작한다. 이때 방문한 정점은 방문되었다는 표시를 해주고, 탐색은 방문하지 않은 정점으로 계속된다. 더 이상 방문하지 않은 정점이 없다면 가장 마지막에 방문한 정점으로 돌아가서 그곳에서 다시 방문하지 않은 인접 정점을 찾아간다. 깊이 우선 탐색은 재귀 호출을 통해 구현된다.

(a) A에서 시작: A→B
(b) B→D (A는 이미 방문)
(c) D→C (B는 이미 방문)
(d) C→E (A, D는 이미 방문)
(e) E→G (C는 이미 방문)
(f) G→H (E는 이미 방문)
(g) H에서 더 이상 방문할 정점이 없음 (G→E→C→D 로 돌아감)
(h) D→F
(i) F에서 더 이상 방문할 정점이 없음. 탐색 완료.

 

1) 인접 행렬

// 인접 행렬
void DFS(int v) {
    visited[v] = true; // 먼저 방문한 정점 v를 방문 했다고 저장

    cout << v << " ";
    for (int w = 0; w < vtxsize; w++) {
        if (grp[v][w] != 0 && visited[w] == false) { // 아직 가지 않은 정점이면
            DFS(w); // 순환 호출
        }
    }
}

2) 인접 리스트

// 인접 리스트
void DFS(int v) {
    visited[v] = true; // 먼저 방문한 정점 v를 방문 했다고 저장
    cout << vtx[v] << " "; 

    for (GrpNode* w = grp[v]; w != NULL; w = w->link) {
        if (visited[w->id] == false) { // 아직 가지 않은 정점이면
            DFS(w->id); // 순환 호출
        }
    }
}

깊이 우선 탐색의 경우도 시간 복잡도는 인접 행렬 \(\Theta(n^2)\), 인접 리스트 \(\Theta(n + e)\)의 시간이 소요된다.

 

 

[Reference]

문병로, 「쉽게 배우는 알고리즘」 (한빛 아카데미, 2018)

 

 

728x90