[ 알고리즘 ] 12. DFS

 Depth First Traversal

 

들어갈 수 있는만큼 최대한 들어갔다가 나오는 것

 

● BFS = Level order   

→  같은 레벨들 차례차례 보고 내려감

 

● DFS = Pre in Post order로 할 수 있음

→ 인접해있는 아래 노드로 쭉 내려감

→ 다 Explore 했으면, Backtrack 하여 돌아온다.

    = 어디서 왔는지 알아야 함 

    = Stack 형식으로 구현한다.

 

 

 

 

---

 

특징)

 

1. 인접한 Vertex가 이미 Discover되었다면,

     그 사이에 있는 Edge는 Explore는 되지 않지만, Check는 되었다고 할 수 있다.

 

2. 색깔별 의미

    ● White  : Discover되지 않음

    ● Gray    : Discover 되었지만 작업하지는 않음  ( 얘 기준으로 더 파고들 곳이 있음 ) 

    ● Black   : Finish 됨   (파고들 곳 다 보고 나왔음 = 여기로 더 안 가도 됨)

 

Discover된 시간과 Finish 된 시간을 나눠서 생각한다.

 

  

 

 

얘네도 Psudo code

 

[ 왼쪽 ]

● 위에 for는 V에 있는 모든 vertex Initialization

 

● Time은 전역변수

 

● V에 있는 vertex들을 하나하나 보면서,

     해당 vertex의 색이 White라면 DFS-VISIT 함수에 해당 vertex를 넣는다.

 

 

[ 오른쪽 ]

● 우선 색을 바꾸고, Time을 추가한 뒤에 해당 vertex Discover time에 기입한다.

 

● 인접한 vertex를 보고 White라면 다시 현재 함수에 넣는다.

 

● 인접한 vertex들에 대한 방문이 다 끝났다면 

   시간을 한 번 더 추가하고 해당 vertex Finish time에 기입 후, 검은색으로 바꾼다.

 

 

직접 스택을 사용하기보단 

재귀함수를 스택처럼 사용함

 

 

---

 

예제 

 

우리가 BFS 예제에서는 수많은 사람이 한 턴마다 각자 원하는대로 한 다리씩 건너서 다른 섬으로 가는 방식으로 표현했다.

 

DFS에서는 한 사람이 섬을 돌아다닌다고 생각하면 된다.

= 모든 Island는 Discovered Time이 다르다.

 

 

Src vertex 의 Discovery time을 1로 설정 + Gray

 

 > 인접한 Vertex가 White이므로 그 Vertex를 또 Visit하는 함수 Call

 

▼

 

Discovery time을 2( 1+1 ) 로 설정 + Gray

 

 > 인접한 Vertex가 White이므로 그 Vertex를 또 Visit하는 함수 Call

 

▼

Discovery time을 3( 2+1 ) 로 설정 + Gray

 

 > 인접한(갈 수 있는) Vertex 중에 White가 없다.

 > Black으로 만들면서 Back Tracking 한다.

      → Finished time 4 (3+1) 로 설정 + Black 

 

 

Back tracking 한 다음 Vertex에서 다시 반복문을 돈다. 

인접한 Vertex 중에 White로 간다...

 

...

 

 

결과

 

이거 꼭 해보기

 

---

연습 문제

 

 

해봐라.

여러 개가 있다면 Visit 순서는 알파벳 순으로 한다.

 

답 ▼

더보기

 

---

DFS(G) 에서

1번 for = Vertex 초기화

2번 for = 안에 있는 Vertex 중에 White인 Vertex들 Visit

 

DFS-VISIT에서

for = 현재 Vertex에 인접한 Vertex가 White이면, 

         그 Vertex Visit (재귀 함수) 

 

 

---

DFS에서의 특징

1. 서로 같은 레벨 혹은 Subtree들 끼리는 Disjoint 하기 때문에

     2번 카운트 하는 것에 대한 고려를 할 필요가 없다.

 

 

2. Edge는 One-way 이다 

    단방향임. + Tree이면 Cycle이 존재하지 않는다.

 

3. (Tree의 특성)

    : N개의 Vertex, N-1개의 Edge, 모두 Connected 여야 함

 

 

 

Pre-Order : 나 먼저 하고 , 자식들 Search

Post-Order : 자식들 먼저 하고 , 나  Search

 

여기에서 In-Order는 안 함 : 자식이 몇 개일지 몰라서

 

---

 

괄호 관련 이론...

d = 여는 괄호

f = 닫는 괄호라고 생각하고 보면 된다.

 

 

Tree 그리면서 해보기

 

 

---

 

Edge의 종류

 

● Tree Edge

새로운 Vertex ( 흰색으로 되어있는 거 ) 를 만나는 Edge

    > Edge를 Explore 하면서 Tree(들)을 만든다.

    > Tree Edge는 Cycles이 안 된다. (Tree의 특성) 

 

 

 

빨간 선들이 Tree Edge이다.

 

 

● Back Edge

자식 → 부모 Vertex로 가는 Edge

 

주로 양상은 Gray → Gray가 된다.

 

 

 

 

● Forward Edge

밑으로 다 가서 검은색으로까지 만들고 왔는데

그 검은색 노드까지 한 번에 가는 Edge

 

주로 양상은 Gray → Black 이다.

 

내려가더라도 Tree형태가 아니다.

 

 

 

● Cross Edge

Tree나 SubTree 사이를 이어주는 Edge

 

주로 양상은 Gray → Black 이다.

 

이런 모양이다.

왼쪽 Subtree에서 오른쪽 Subtree로 가는 Edge.

근데 Subtree의 관계이기 위해서는 Edge로 가서 작업하고 FInish되면 안 되므로

위 사진에서는 오른쪽 Subtree먼저 마치고 왼쪽 Subtree에서 작업하다가 

Cross Edge로 들어가서 Black을 확인하고 나온다.

 

(요약: Edge가 있는 곳이 나중에 작업되어야 함)

 

Forward Edge와 Cross Edge를 가르는 기준은

Gray → Black일 때, Gray가 Black의 Parent인지에 따라

 

 

---

 

 

 

 

 

색으로는 뭐 그냥 판단할 수 있음.

 

근데 색이 없으면 어떻게 판단할거임??

 

→ Discover Time 이랑 Finished Time 을 비교한다.

 

---

 

만약 Edge가 2번 Processed되어도 상관이 없다면 2개의 Direct Edge로 바꾼다.

 

 

Undirect Graph이면 Tree Edge와 Back Edge만 가능하다.

 

 

증명

 

 

---

BFS / DFS

 

 

 

 

 

(출처)

한동대학교 용환기교수님 - 알고리즘