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

이번 글에서 다뤄볼 내용은 그래프 탐색 기법 중 하나인 DFS(깊이 우선 탐색)입니다. 

 

정의 

• 그래프에서 어떤 노드에 인접한 노드 중 하나를 선택해서 해당 노드와 연결된 노드를 더 이상 탐색할 수 없을 때까지 탐색하는 알고리즘

 

동작 과정 

1. 현재 노드를 방문처리한다.
2. 현재 노드와 연결된 노드 중 방문처리되지 않은 노드를 하나 선택한다. 
   1. 만약 방문처리되지 않은 노드가 존재하지 않는다면 이전 노드로 돌아간다. 
3. 선택된 노드를 현재 노드로 한다. 
4. 1~3을 그래프의 모든 노드를 탐색할 때까지 반복한다. 

 

구현

// 시간복잡도는 O(노드수 + 간선수)이다. 

#include <iostream>
#include <vector>

using namespace std:

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

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

 

이상으로 DFS에 관한 내용을 마치겠습니다. 

읽어주셔서 감사합니다.