[알고리즘] 그래프 순회 문제 - 1. 깊이 우선 탐색(DFS)

'코딩 테스트를 위한 자료 구조와 알고리즘 with C++' 를 참고하여 작성하였습니다.

1. 그래프 ; Graph

1.1 개념

그래프 순회 문제를 들어가기 전 짧게 그래프에 대해 설명하자면, 그래프는 정점(vertex)의 집합과 정점들을 서로 잇는 간선(edge)의 집합으로 구성된 자료구조로 연결되어 있는 객체 간의 관계를 표현할 수 있다. 수학적으로는 G = <V, E>(v는 정점, e는 간선의 집합) 형태로 표현할 수 있다. 간선 방향의 유무에 따라 방향 그래프(directed graph)와 무방향 그래프(undirected graph)로 나눌 수 있고, 간선의 가중치 유무에 따라 가중 그래프(weighted graph)와 비가중 그래프(unweighted graph)로 나눈다.

2. 그래프 순회 문제 ; Graph Traversal Problem

2.1 개념

그래프 순회 문제는 그래프의 한 정점에서 시작하여 남은 모든 정점을 방문하는 문제를 의미한다. 또한 특정한 정점을 찾기 위해 사용될 수 있기 때문에 그래프 탐색 문제(graph search problem)라고도 한다. 각각 정해진 순서로 모든 정점을 방문하는 여러 그래프 탐색 알고리즘들이 있는데, 그 중 가장 잘 알려진 알고리즘에는 다음 두 개가 있다.

 

1. 깊이 우선 탐색(Depth-First Search)

2. 너비 우선 탐색(Breadth-First Search)

 

2.2 그래프 순회 알고리즘

2.2.1 깊이 우선 탐색 ; Depth-First Search

깊이 우선 탐색(DFS)은 시작 정점에서부터 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식을 의미한다. 더 방문할 정점이 존재하지 않으면 다시 뒤로 돌아가 다른 경로를 찾아간다.

그래프 예시

다음과 같은 모양의 그래프가 있다고 가정한다. 0번째 정점을 시작으로 작은 값부터 찾아간다고 가정했을 때, DFS 알고리즘을 적용하면 다음과 같은 순서로 진행된다.

1단계 : 0번 정점 방문

2단계 : 0번 정점과 인접한 정점 중 가장 값이 작은 1번 정점 방문

3단계 : 1번 정점과 인접했고, 아직 방문하지 않은 정점 중 가장 값이 작은 2번 정점 방문

4단계 : 2번 정점과 인접했고, 아직 방문하지 않은 정점 중 가장 값이 작은 3번 정점 방문

5단계 : 3번 정점과 인접했고, 아직 방문하지 않은 정점 중 가장 값이 작은 4번 정점 방문

6단계 : 4번 정점과 인접했고, 아직 방문하지 않은 정점인 6번 정점 방문

7단계 : 6번 정점과 인접했고, 아직 방문하지 않은 정점인 5번 정점 방문. 이후 더 이상 방문하지 않은 정점이 존재하지 않으므로 DFS 종료.

따라서 위의 그래프를 DFS를 통해 순회하였을 때 0 ➡️ 1 ➡️ 2 ➡️ 3 ➡️ 4 ➡️6 ➡️ 5 순서로 방문한다.

 

2.2.2 깊이 우선 탐색 코드

깊이 우선 탐색을 구현하는 데 스택을 사용하기도 하고 재귀 함수를 사용하기도 하는데, 재귀 호출 방식을 선택하였다. 정점과 간선 정보가 담긴 1차원 정수 배열 벡터 graph와 방문 여부를 표시하는 bool 벡터 visited를 이용하여, 방문할 정점을 선택한 뒤 DFS를 실행한다. 시간 복잡도는 O(V + E) (V : 정점의 개수, E : 간선의 개수)로 BFS와 동일하다.

시작점으로부터 특정 경로를 따라 이동하기 때문에 멀리 떨어져 있는 정점을 찾을 때 적합하다.

void DFS(int vertex) {
    visited[vertex] = true;
    printf("%d ", vertex); // 방문 정점 출력
    for(int i = 0; i < graph[vertex].size(); i++) {
        int next = graph[vertex][i];
        if(!visited[next])
            DFS(next);
    }
}

 

위의 함수를 이용한 전체 코드는 다음과 같다. 정점과 간선 입력 방식은 백준 1260번 DFS와 BFS를 이용하였다.

#include <cstdio>
#include <vector>
#define MAX 1001

using namespace std;

vector<int> graph[MAX];
vector<bool> visited(MAX, false);

void DFS(int vertex);

int main(void) {
    int v, e, start;
    scanf("%d %d %d", &v, &e, &start);

    visited.resize(e + 1);
    
    for(int i = 0; i < e; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    DFS(start);
    
    return 0;
}

void DFS(int vertex) {
    visited[vertex] = true;
    printf("%d ", vertex);
    for(int i = 0; i < graph[vertex].size(); i++) {
        int next = graph[vertex][i];
        if(!visited[next])
            DFS(next);
    }
}​