깊이 우선 탐색 알고리즘(DFS)

깊이 우선 탐색은 깊은 것을 우선적으로 탐색하는 알고리즘입니다.

last in first out구조의 스택을 사용해 구현할 수 있습니다.

 

우선 1을 방문 처리해 스택에 넣어줍니다.

 

스택에서 최상단 노드를 확인하고(여기서는 1이겠죠.)

연결된 노드가 있다면 그 노드를 스택에 넣어줍니다.

만약 방문하지 않은 연결된 노드가 없다면 마지막으로 들어온 것부터 하나하나 꺼내면서 위의 과정을 반복합니다.

이 과정을 연결된 모든 노드를 한 번씩 살펴볼 때까지 반복합니다.

1에 방문합니다.

그러면 스택에 1이 들어갑니다.

[1]

이제 1과 인접한 수중 가장 작은 2를 방문하고 스택에 넣어줍니다.

[2,1]

2와 인접한 수중 가장 작은 3을 방문하고 스택에 넣어줍니다.

[3,2,1]

위와 같은 과정을 반복하면

[6,3,2,1]

[7,6,3,2,1]

7까지 방문할 수 있습니다.

7은 방문하지 않은 연결 노드가 없습니다.

스택에서 가장 최근에 들어간 노드부터 빼기 시작합니다.(last in first out)

[6,3,2,1]

6,3은 7과 마찬가지입니다.

2는 4가 남아있습니다.

이제 [4,2,1]이 남고

[5,4,2,1]이 됩니다.

5는 방문하지 않은 연결된 노드가 없습니다.

4,2,1 역시 마찬가지이죠.

이제 다 빠지게 됩니다.

방문 순서는 1-2-3-6-7-4-5입니다.

이렇듯 연결된 노드 중 가장 깊은 곳까지 탐색합니다.