DFS(Depth - Fist Search) : 개념, 예시

0. 그래프란?

---

node와 node를 edge로 연결한 비선형 자료구조,. 즉 객체관의 관계?를 나타내는 방법

 

1. 그래프 탐색

---

그래프 안에 어떤 노드가 있는지 알아보는 방법. 어느 한 노드부터 시작하여 모든 노드를 한 번씩 방문!

 

2. 그래프를 maxtirx로 나타내기

---

예를들어 "2"와 인접한 노드를 확인해보자. "2"와 인접한 노드는"0", "5", "6"이다.

즉 (2, 0), (2, 5), (2, 6)에 1을 입력한다. 만약 가중치가 부여된다면 해당 값 입력하면 됨.

 

위의 그래프는 양방향으로 이동이 가능하다. 즉, (0, 2), (5, 2), (6, 2)에 "1"이 똑같이 입력된다.

따라서 해당 matrix는 symmetric하다.

단, 그래프가 방향성이 있을 경우 , symmetric하지 않다.

 

1. DFS(Depth - Fist Search) 깊이우선 탐색 :

---

한 노드에서 시작하여 다음 branch까지 해당 branch는 모두 탐색하는 방법.

깊이 방향으로 탐색함.

 

 

예를들어 0에서 탐색을 시작한다고 하자. 0은 그래프를 돌아다니면서 탐색을 한다.

돌아다니는 애를 traverse라고 부른다.

 

0부터 시작하는데 그다음은 1로 간다고 해보자.

 

새로운 갈림길에서 한 쪽으로 끝까지 깊이 방향으로 탐색해간다.

 

만약 더 이상 진행이 불가능 하다면, 가장 최근 갈림길?로 이동하여 다른 길로 탐색을 시작한다.

 

그리고 방문한 node는 따로 표시를 해둔다.

 

위와 같은 규직으로 지행을 하면 다음과 같은 순서로 탐색하게 된다.

 

 

 

 

2. DFS를 stack으로 나타내기

---

DFS는 Stack으로 나타낼 수 있다.

 

그 이유는, Stack은 가장 최근의 데이터만 불러올 수 있기 때문에

 

가장 최근의 brance를 불러오는데 사용할 수 있기 때문이다.

 

한마디로 stack의 top에 있는 node가 다음에 갈 node이고,

해당 node에 도착해서 pop을 하면 그 node와 인접한 nodes를 push해야 한다.

 

해당 행위를 반복하면, 인접한 노드를 차례대로 모두 방문이 가능하다.

 

1) "0" 에 방문했다. stack에 첫 번째 node인 "0"을 push.

 

2)이제 "0"에 인접한 "1"과  "2"중 한 쪽을 선택해야 한다.

현재 node를 pop하고 인접 node를 push하자. 순서는 노상관.

 

3)다음에 갈 곳을 선택하자. stack에서 pop을 하면 "1"이 선택된다.

즉 인접한 노드인 "1"로 간다. 그리고 "1"과 인접한 node를 push한다.

4) stack에서 pop을하면 "4"가 나온다. 다음은 "4"이고 "4"와 인접한 노드를 push한다.

엇? "4"에 인접한 노드 중 "1"은 이미 방문했다. 따라서 "5"만 push하면 된다.

 

4) stack에서 pop을하면 "5"가 나온다. 다음은 "5"이고 "5"와 인접한 노드를 push한다.

엇? "5"에 인접한 노드 중 "4"은 이미 방문했다. 따라서 "2"만 push하면 된다.?

"2"는 이미 stack에 존재한다. 즉 더이상 갈 곳 이 없다.

 

5) 다른 길을 찾기위해 가장 최근의 갈림길로 돌아가서 다른 길로 가야한다.

이 경우에 1로 돌아가서 3으로 진행해야 한다.

stack에서 pop을하면 "3"가 나온다. 다음은 "3"이고 "3"와 인접한 노드를 push한다.

6) "3"과 인접한 다음 노드인 "7"로 이동한다. 

stack에서 pop을하면 "7"가 나온다. 다음은 "7"이고 "7"와 인접한 노드를 push한다?? 갈 수 있는 인접한 노드가 없다.

더이상 갈 곳이 없다.

7) 가장 최근의 갈림길로 돌아간다. "0"에서 아까는 "1"로 갔으니 이번엔 "2"로 간다.

즉 stack 에서 pop을 하면 "2"가  나오는 것 과 같다. 다음은 "2"로 이동하고 "2"와 인접한 노드를 push.

8) 이제 마지막으로 "6"으로 가자. stack에서 pop을 하면 "6"이 나온다.

 

9) 0 --> 1 --> 4 --> 5  --> 3  --> 7  -->  2  -->  6  순서로 모두 탐색하였다.

  근데 별로 좋은 순서같지는 않다. 흠....