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

Graph 탐색 : 하나의 vertex로 부터 시작하여 차례대로 모든 vertex들을 한 번씩 방문하는 것. / 예) 특정 도시에서 다른 도시로 갈 수 있는가, 전자 회로에서 특정 단자끼리 서로 연결 되어 있는가

 

Depth-First Search(DFS, 깊이 우선 탐색) :

root 노드(혹은 다른 임의의 노드)로부터 시작해서 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하는 방법. / 미로 탐색시 한 방향으로 갈 수 있을때까지 계속 가다가 더 이상 갈수 없을때, 다시 가장 가까운 갈림길로 돌아와서 이곳에서 다른 방향으로 다시 탐색을 진행하는 방법과 유사함. / 넓게(wide하게) 탐색하기 보다는 깊게(deep하게) 탐색하는 것. / 모든 node를 방문하고자 하는 경우에 이 방법 사용. / DFS가 BFS보다 좀 더 간단함. / 단순 탐색 속도 자체는 DFS가 BFS에 비해 느림.

 

Depth-First Search 특징, 장점과 단점 :

- recursive한 형태를 가지고 있음. / Pre-Order Traversal을 포함한 다른 형태의 트리 traversal은 모두 DFS의 한 종류이다. / 그래프 탐색할 때 어떤 노드를 방문했었는지 여부를 반드시 검사 해야함. (검사하지 않을 경우 무한 loop에 빠질 위험 있음) 

장점 : 현 경로상의 노드만을 기억하면 되므로 저장공간의 수요가 비교적 적음. / 찾고자하는 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있음.

단점 : 해가 없는 경로에 빠질 수 있거나 얻어진 해가 최단 경로가 된다는 보장이 없음. / 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음 경로로 탐색하는 방법이 유용할 수 있음. / 목표에 이르는 경로가 다수일떄 DFS는 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있음.

 

 

Depth-First Search의 과정 :

1. 노드 a(시작 노드) 를 방문. (방문한 후에는 표시) 

2. a와 인접한 노드들을 차례로 traverse. (a와 인접한 노드가 없을땐 종료)

3. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 함. (b를 시작점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문함)

4. b의 branch들을 전부 탐색했다면, 다시 a에 인접한 노드들 중에서 아직 방문이 안 된 노드를 찾는다. -> b의 branch들을 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드들을 방문할 수 있다는 뜻. / 아직 방문이 안 된 노드가 없으면 종료.  있으면 그 노드를 시작점으로 DFS실행.

 

Depth-First Search의 시간 복잡도

- DFS는 그래프의 모든 edge를 조회함. / 인접리스트로 표현된 그래프 : O(Vertex수 + edge의 수) / 인접행렬로 표현된 그래프 : O(Vertex수^2) / -> 그래프 내에 적은 숫자의 edge만을 가지는 Sparse Graph(희소 그래프)의 경우는 인접 리스트가 인접 행렬보다 유리함. 

 

Depth-First Search의 구현 :

- Recursive Function / Stack

Stack - 탐색 시작 노드를 stack에 삽입하고 방문처리 > stack의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 stack에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면 stack에서 최상단 노드를 꺼냄. > 끝날때까지 반복.