[알고리즘] 깊이 우선 탐색 DFS 알고리즘 (Depth First Search)

DFS 알고리즘 (Depth First Search)

 

깊이 우선 탐색(DFS)은 BFS와 달리 스택 자료구조를 사용하여 깊이를 우선적으로 탐색하는 알고리즘입니다. 또한 재귀적 함수로도 구현이 가능합니다.

위와 같은 이진 트리에 대하여 깊이 우선 탐색을 해보겠습니다.

깊이 우선 탐색은 기본적으로 노드를 스택에 넣고 인접한 노드 중 방문하지 않은 노드를 스택에 넣고 방문이 완료되었으면 다시 방문하지 않은 노드를 찾아서 스택에 넣는 방식입니다. 가장 먼저 방문하는 노드 1을 스택에 넣고 방문 완료(visited)합니다. 스택은 큐와 달리 나중에 들어온 것이 먼저 나가는 후입선출 방식입니다.

인접해있던 노드 2를 스택에 넣고 방문 완료합니다.

위 과정을 통해 노드 7까지 스택에 삽입되었다면 노드 7, 6, 3은 스택에서 나가게 됩니다. 

이후 방문되지 않은 노드4와 5를 찾아서 스택에 넣습니다. 모든 노드의 방문이 완료되었으므로 스택에서 노드가 하나씩 나가게 됩니다. 방문 탐색 순서는 1 - 2 - 3 - 6 - 7 - 4 - 5 입니다.

 

알고리즘 구현

// Algorithm Analysis
// 깊이 우선 탐색 (Depth First Search)

#include <iostream>
#include <vector>

using namespace std;

int num = 7; // 전체 노드 수
int visited[8]; // 방문 체크용 배열. [0]은 미 사용
vector<int> arr[8]; // 인접한 노드를 연결할 배열

void dfs(int x) {
	if (visited[x]) return;
	visited[x] = true;
	cout << x << " ";
	for (int i = 0; i < arr[x].size(); i++) {
		int j = arr[x][i];
		dfs(j);
	}
}

int main() {
	arr[1].push_back(2);
	arr[2].push_back(1);

	arr[1].push_back(3);
	arr[3].push_back(1);

	arr[2].push_back(3);
	arr[3].push_back(2);

	arr[2].push_back(4);
	arr[4].push_back(2);

	arr[2].push_back(5);
	arr[5].push_back(2);

	arr[3].push_back(6);
	arr[6].push_back(3);

	arr[3].push_back(7);
	arr[7].push_back(3);

	arr[4].push_back(5);
	arr[5].push_back(4);

	arr[6].push_back(7);
	arr[7].push_back(6);

	dfs(1); 
}
// 1 2 3 6 7 4 5

구현에는 스택 STL을 사용하지 않고 재귀적 함수로 구현하였습니다.

 

 

* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.