[알고리즘] 깊이 우선 탐색(DFS)이란

안녕하세요, 여행벌입니다.

오늘은 그래프 탐색 기법 중 깊이 우선 탐색(DFS)에 대해서 포스팅해보겠습니다.

---

깊이 우선 탐색(DFS)

 깊이 우선 탐색은 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 탐색을 진행하는 순회 방법입니다. 깊이 우선 탐색은 재귀 함수를 이용해 구현하고 너비 우선 탐색과 마찬가지로 방문한 정점들을 체크하는 bool 배열이 필요합니다.

예시

 DFS 탐색은 다음과 같은 순서로 진행됩니다.

 1) 현재 탐색 중인 노드와 연결된 노드 중, 방문하지 않은 노드가 있다면 방문하지 않은 노드로 재귀 함수를 호출하며 탐색을 진행.

 2) 1의 과정을 가능한 모든 노드를 탐색할 때까지 반복한다.

 너비 우선 탐색과는 다르게 현재 탐색 중인 노드에서 연결된 노드로 탐색을 진행하지, 시작 노드에서 가까운 노드부터 탐색을 진행하지 않습니다.

코드 구현 (C)

인접 행렬로 표현된 그래프에 대한 DFS

bool visited[MAX_VERTIECES];

void dfs_mat(GraphType* g, int v) {
	visited[v] = TRUE;
	printf("%d 노드 탐색 중 \n", v);
	for (int w = 0; w < g->n; w++)
		if (g->adj_mat[v][w] && !visited[w])
			dfs_mat(g, w); // 재귀점으로 다음 노드 호출.
}

인접 리스트로 표현된 그래프에 대한 DFS

void dfs_list(GraphType* g, int v) {
	GraphNode* w;
	visited[v] = TRUE;
	printf("%d 노드 방문 중\n", v);
	for (w = g->adj_list[v]; w; w = w->link)
		if (!visited[w->vertex])
			dfs_list(g, w->vertex);
}

코드 구현 (C++)

2차원 배열로 표현된 그래프에 대한 DFS

int graph[MAX_VERTICES][MAX_VERTICES];
bool visited[MAX_VERTICES];

void dfs_mat(int v) {
	visited[v] = TRUE;
	cout << v << "노드 탐색 중 \n";
	for (int w = 0; w < MAX_VERTICES; w++)
		if (graph[v][w] && !visited[w])
			dfs_mat(w);
}

벡터 배열로 표현된 그래프에 대한 DFS

vector<int> graph[MAX_VERTICES];
bool visited[MAX_VERTICES];

void dfs_mat(int v) {
	visited[v] = TRUE;
	cout << v << "노드 탐색 중 \n";
	for (int w = 0; w < graph[v].size(); w++)
		if (graph[v][w] && !visited[w])
			dfs_mat(w);
}

 정점의 수가 너무 커 그래프를 2차원 배열로 표현할 수 없는 경우, 벡터 배열로 표현해야만 그래프를 표현할 수 있으므로, 벡터 배열로 표현하는 그래프에 대한 DFS를 익혀두시면 알고리즘 문제를 푸는데 도움이 될 것 같습니다.

깊이 우선 탐색의 시간 복잡도 분석

 정점의 수가 n이고 간선의 수가 e인 그래프

● 그래프가 인접 리스트로 표현되어 있는 경우 O(n + e)

● 그래프가 인접 행렬로 표시되어 있는 경우 O(n^2)

---