[Algorithm] DFS 정리

 

1. DFS란?

- DFS 는 깊이 우선 탐색 을 말합니다.

- 루트 노드에서 시작하여, 해당 노드들의 자식을 우선적으로 탐색합니다.

* 미로찾기로 예시를 들면, 한 방향으로 갈 수 있을 때까지 계속 가다가 더이상 갈 수 없게 되면 다시 가까운 갈림길로 되돌아 와서 다시 탐색을 진행하는 것과 유사합니다.

 

 Q. 깊이우선 탐색을 하면 순서가 어떻게 될까요?

 

 A. 0-1-3-4-2-5-6

 

 

 

 

 

 

 

 

 

1) 특징

> 모든 노드를 탐색할 때 좋은 방법입니다.

> BFS보다 좀 더 간단하지만 느립니다.

 

 

2) 알고리즘 구현 방법

 

DFS의 결과 :

1 - 2 - 3 - 5 - 4 -6

 

 

 

 

 

 

ⓐ 재귀함수 이용

#include <iostream>
#include <vector>
using namespace std;

bool visited[10]; //방문했던 노드를 기억하는 배열선언
vector<int> v[10] = { {}, {2,6},{1,3,4,5},{2,4,5},{2,3,5},{3,4},{1,2} }; //인접노드 벡터선언
void DFS(int now) {
	visited[now] = 1; //now를 방문했으면 1
	printf("%d번 노드를 방문하였습니다.\n", now);
	for (int i = 0; i < v[now].size(); i++) { //인접노드의 개수만큼 반복
		int next = v[now][i]; //
		if (!visited[next]) DFS(next); //만약 방문하지 않았던 노드면 다시 함수 호출
	}
}

int main() {
	DFS(1); //1부터 시작
}

- 과정 

1. DFS(1) 
2. dfs함수의  now에 1이들어가고 "1번노드를 방문하였습니다." 출력
3. 1번의 인접 노드가 2개이므로 for문 2번 반복.
4. next = 2 
5. next는 방문하지 않았으므로 dfs함수에 2가 들어간다. 
6. now= 2가 된다. (2번 노드를 방문하였습니다 출력)
7. 2번의 인접노드가 4개이므로 for문 4번 반복
8. next =1, 하지만 방문한 노드임
9. next = 3 
10. 3은 방문하지 않은 노드이므로 dfs에 3이 들어간다
11. now = 3가 된다.
12. 3의 인접노드가 3개이므로 for문 3번반복한다.

… (이하생략)

---

시간복잡도 : 모든 정점을 방문해야 하므로 DFS 함수는 총 정점의 개수 V번 호출된다.

                 DFS함수는 그 안의 for문에 의해 각 정점마다의 인접정점의 개수만큼 방문하므로 총 인접정점의 개수는                     간선의 개수 E이므로, O(V+E)만큼 걸리게 된다.