깊이우선탐색 (Depth First Search)

DFS는 자기가 방문했던 자취를 기억하는 스택의 특징을 이용하여 

인적한 노드부터 차례대로 그래프를 순회하는 방법이다.

주어진 그래프에서 1부터 DFS를 한다고 예시를 들어보자.

여기에서는 더 작은 숫자가 먼저 탐색한다고 가정하면,

2와 6중에서 2를 먼저 방문하게 된다.

2에서 다시 DFS를 시행하는데, 방문할 노드가 3과 6이 있으므로

더작은 3을 방문하게 되고,

3에서 DFS를 다시 시행하여 4를 방문하고, 4에서 다시 DFS를 해서 5를 방문한다.

이제 5에서 더 방문할 곳이 없기 때문에 그 동안 왔던 순서 대로

5 --> 4 --> 3--> 2 로 돌아간다.

2로 다시 돌아와서 DFS를 하면 3과 6을 탐색하려고 하는데,

3은 이미 방문한 노드이기 때문에 6을 방문한다.

6까지 방문하고 6에서 DFS를 해보면 1 과 2를 보는데,

둘다 방문한 노드이기 때문에 다시 2로 돌아간다.

2에서도 이제 모두 방문했기 때문에 1로 돌아가서 DFS를 마치게 된다.

한번더 이해를 하기 위해서 위와 같은 방식으로 DFS를 해보자.

1 --> 2 --> 3 --> 5 --> 6 --> 7 --> 8 --> 9 --> 4

이제 4에서 1과 2는 모두 방문했기 때문에 다시 8까지 돌아온다.

8에서 10을 방문하고 10을 방문했다고 표시하고 나서, 더 이상

방문할 곳이 없기 때문에 2까지 돌아온다.

2에서는 11을 방문할 수 있기 때문에 11을 방문하고 다시 돌아와서 DFS를 마치게 된다.

---

DFS의 과정은 먼저 방문했던 노드에는 방문했다고 처리를 한다.

그리고 인접한 모든 노드 중에 방문하지 않은 노드에서 DFS를 처리하면 된다.

DFS 함수의 구현과정은 먼저 함수 인자로 인접리스트로 구현된 graph, 노드번호 x, 방문여부 visited가 필요하다

예를 들어 1에서 시작했다고 해보자. 그러면 x 노드의 방문여부를 true로 설정 한다.

x의 인접노드는 2와 4 순서대로 저장되어 있다고 할 때, 처음에 y에 2가 저장되고,

visited[2]가 아직 false이기 때문에 2에서 DFS를 다시 시행한다.

DFS 함수를 이런식으로 동작한다.

---

DFS를 처음 공부하기 때문에 자세하게 과정을 적다보니 사진이 많아졌다. 

중요하기 때문에 구체적인 과정을 통해서 확실한 이해가 필요하다.

위의 사진은 인접리스트로 graph를 입력받고,  visited[] 를 모두 F로 초기화 해놓은 상태이다.

이제 1에서 DFS를 시작해보면서 하나하나의 과정을 살펴보자.

1에서 DFS를 하면 visited[1]이 True로 바뀐다. 그리고 1의 인접노드를 탐색한다. 

즉, 0부터 graph[1].size인 2까지 반복문을 수행한다. 처음에 그럼 y에 1의 첫 인접노드인 2가 들어가고,

visited[2]가 false이기 때문에 DFS(2)가 호출된다.

DFS(2)가 호출되면, visited[2]를 True로 바꾸고, 2의 인접노드들인 1, 3, 4 순서대로 반복문이 수행되는데,

2의 첫번 째 인접노드인 1은 이미 방문되어있는 상태이기 때문에,

i가 1증가해서 i=1이 되어서 y에 3이 들어간다. 그런데 3은 아직 방문하지 않아서

False상태이기 때문에 3에서 다시 DFS를 수행한다. 이 때 DFS는 재귀함수 이기 때문에

DFS(1)은 아직 끝나지 않고 계속 DFS(2)가 끝나기를 기다리고 있는 상태이다.

DFS(3)이 호출되면, visited[3]을 True로 바꾸고, 3의 인접노드인 2, 5, 6, 7을 탐색하는데,

2는 이미 방문되어 있는 상태이고, 5가 방문되지 않은 상태이기 때문에

5에서 다시 DFS를 한다.

DFS(5)를 할 때, 5의 인접행렬인 3은 이미 방문되었다고 표시되어있기 때문에

DFS(5) 안에 있는 반복문이 돌아서 DFS(5)는 끝나게 된다.

여기서 중요한점은 재귀호출이기 때문에 DFS(3)이 DFS(5)를 기다리고 있었다.

DFS(5)가 끝나면 이제 다시 DFS(3)으로 돌아온다.

DFS(3)에서 노드 3의 인접행렬 2, 5까지 끝나고나서,

다음 6을 방문했는지 안했는지 검사를 한다. visited[6]은 아직 false이기 때문에

DFS(6)을 시행한다.

이 상태에서는 아직 DFS(1)이 DFS(2)가 끝나기를 기다리고 있고,

DFS(2)가 DFS(3)이 끝나기를 기다리고 있는 상태이다.

만약에 DFS(3)이끝나고 DFS(2)한테 끝났다고 알려주게 된다면,

DFS(2)는 노드 4에서 DFS를 수행할 것이다.

다시 원래대로 돌아와서 DFS(6)을 할 때, 6의 인접노드 3은 이미 방문되었다.

그 다음인 7은 아직 방문이 안되어 있는 상태이기 때문에 7에서 DFS를 한다.

노드 7에서 역시 인접노드 3은 방문한 상태이고,

6도 역시 방문된 상태이기 때문에 

DFS(7)이 끝나게 된다.

다시 DFS(6)으로 돌아와보면, 6의 인접노드 3, 7까지 탐색을 모두 끝났기 때문에

DFS(6)도 끝나게 된다.

DFS(6)이 끝나면 다시 DFS(3)으로 돌아온다.

노드 3의 다음 인접노드 7역시 방문한 상태이기 때문에

3의 인접노드는 모두 다 탐색을 했고, DFS(3)이 드디어 끝나게 된다.

DFS(2)로 돌아와서 보면 인접노드 1, 3까지 탐색을 끝낸 상태이고,

이제 다음 4가 남아있기 때문에 DFS(4)를 한다.

DFS(4)를 하면 4의 인접노드인 1을 확인하게 되는데, 이미 방문되어 있는 상태이다.

그 다음으로 2 역시 방문되어 있는 상태이기 때문에 이대로 DFS(4)는 끝나게 된다.

그러면 DFS(2)도 끝나고, DFS(1)역시 끝나서 그래프의 순회가 마무리 된다.

결국에 순회한 결과를 보면  위의 순서대로

1 --> 2 --> 3 --> 5 --> 6 --> 7 --> 4 순으로 한것을 볼 수 있다.

---

DFS의 시간복잡도는 노드가 6개고 간선의 개수가 7개인 그래프를 예를들어 설명해 보자.

위의 그래프에서 DFS를 수행해보면 총 20번의 연산이 수행되는데, 20번이라는 연산은

자기자신을 방문한 횟수 + 자신에서 이웃노드에 한번씩 모두 방문한 횟수를 더한것이다.

근데 2번째 모든 이웃에게 방문하는 것은 모든 간선을 2번씩 지나가는 것인데

그래프의 수학적 공식에서 공부했듯이, 간선의 2배는 차수의 합과 같다.

그래서 노드의 개수 6 + 각각의 차수의 합 14를 더해서 20이 나오는 것이다.

그래서 DFS의 시간복잡도는 O(V+2E)가 되는데, 상수는 의미가 없기 때문에

결론적으로 O(V+E)가 되는 것이다.

출처 : Algorithm LABS