너비 우선 탐색(BFS)와 깊이 우선 탐색(DFS)

이미지 출처 - https://www.quora.com/What-is-the-algorithm-for-BFS-and-DFS

 

 

 

BFS(Breadth-First Search)와 DFS(Depth-First Search)는 그래프 탐색 알고리즘의 두 가지 주요 유형으로, 그래프의 데이터를 탐색하는 데 사용됩니다.

 

이 두 알고리즘을 이해하기 위해서는 그래프가 무엇인지에 대한 개념이 선행되어야 합니다. 그래프에 대한 개념이 부족하신 분들은 아래 포스팅을 참고해주시면 감사하겠습니다.

 

그래프 ( Graph ) 탐색 이론

 

---

너비 우선 탐색 (BFS)

너비 우선 탐색 (BFS) 는 그래프의 시작 정점에서부터 시작하여 인접한 정점들을 먼저 탐색하는 방식입니다.

큐(Queue)를 사용하여 구현되며, 다음과 같은 절차를 따릅니다

 

1. 최초에 시작 정점을 방문하고, 시작 정점과 연결된 다음 정점들을 차례로 큐에 Push합니다. 정확히는 시작 정점도 큐에 넣은 상태에서 큐를 Pop하며 시작합니다. 즉, 큐를 Pop하여 정점을 꺼내는 것은 해당 정점을 방문함을 뜻합니다.
2. 시작 정점을 방문했을 때와 마찬가지로, 큐에서 꺼낸 정점을 방문한 다음, 방문한 정점과 연결된 다음 정점들을 큐에 Push합니다.
3. 위 일련의 과정들을 모든 정점을 방문할때까지 반복합니다.
4. 그리고 그래프가 양방향 그래프이와 싸이클이 포함되어 있는 그래프 같이  방문했던 정점을 다시 방문할 수 있는 경우의 수가 다양하기 때문에 이를 방문했던 정점을 재방문 하는 것을 방지하기 위해, 방문한 정점에 방문처리를 해주고 이후 탐색에서 방문 여부를 확인해야 합니다. 

 

저는 처음 BFS를 공부할 때 글로만 봐서는 BFS를 구현하는데 큐를 이용해야하는 이유와 특히 큐를 이용해서 어떻게 BFS가 구현되는지에 대해 이해하지 못했습니다.

 

그렇기 때문에 저와 같은 분들을 위해 아래 그림들을 통해 큐를 이용해 BFS 동작이 구현되는 과정을 살펴보겠습니다.

 

1. 시작 노드인 1번 정점과 연결된 2번, 3번 정점을 큐에 넣습니다.

위에서 말했듯, 정확히는 시작 정점도 큐에 넣은 상태에서 큐를 Pop하며 시작하지만 이는 그림에서 생략했습니다.

---

 

이제 1번 정점과 연결된 노드들을 모두 큐에 넣고 끝났으니, 큐의 Pop 연산을 통해 다음 정점(2번 정점)을 꺼내어 방문합니다. 마찬가지로 2번 정점과 연결된 다음 정점들을 차례로 큐에 넣어줍니다.

---

2번 정점과 연결된 노드들도 모두 넣고 끝났습니다. 이제 또 다시 큐의 Pop 연산으로 다음 방문할 노드를 꺼내주고

방문한 노드와 연결된 노드들을 차례로 모두 큐에 넣어줍니다.

 

 

 

큐를 보면 위 3번 노드의 방문도 끝이나면 다음 차례는 4번 정점이 될 것임을 알 수 있습니다.

 

 

때문에 모든 탐색이 끝난 뒤 방문이 진행된 방향을 살펴보면

너비를 깊이보다 우선하여 탐색이 진행되었음을 알 수 있습니다.

 

---

깊이 우선 탐색 (BFS)

깊이 우선 탐색 (DFS) 는 그래프의 시작 정점에서 출발하여 한 경로를 따라 최대한 깊이 내려간 후, 더 이상 내려갈 곳이 없으면 되돌아와 다른 경로를 탐색하는 방식입니다. 스택(Stack)을 사용하여 구현되며, 재귀적으로도 구현할 수 있습니다. 절차는 다음과 같습니다.

 

만약 스택으로 구현한다면, BFS 때와 반대로 그래프를 정렬해 두어야 합니다. 만약 재귀함수를 사용해 구현한다면 상관 없습니다. 자세한 이유는 아래에서 살펴보겠습니다.

 

1. 최초에 시작 정점을 방문(스택에 넣은 뒤 Pop)하고 시작 정점과 연결된 정점들을 스택에 넣어준 뒤 연결된 모든 정점을 넣었다면 시작 정점의 방문이 종료됩니다.
2. 큐를 이용해 구현되었던 BFS때와 다르게 스택이 사용되었기 때문에 이번엔 Top 부분에 위치한 정점을 Pop한 뒤 해당 정점을 방문합니다. 마찬가지로 방문한 정점과 연결되어 있는 모든 정점들을 스택에 넣어주며 이번 방문도 종료됩니다.
3. 위 과정들을 방문하지 않은 정점이 남아있지 않을 때까지 반복합니다.

 

그림과 함께 자세히 살펴보겠습니다.

 

1. 시작 노드인 1번 정점과 연결된 2번, 3번 정점을 스택에 넣습니다.

마찬가지로 1을 스택에 넣으며 시작하지만 이는 그림에서 생략했습니다.

 

---

 

 

2. 1번 노드의 방문이 끝났으니, 스택에서 Top에 위치한 3번 정점을 Pop해주어 3번 정점의 방문이 시작됩니다.

그리고 3번 정점과 연결된 6번, 7번 정점들을 Stack에 넣어주며 3번 정점의 방문도 종료되고, 다음 정점인 7번 정점의 방문도 동일하게 이루어집니다.

 

스택의 특성 때문에 2번이 아닌 3번부터, 6번이 아닌 7번부터 탐색하는 것을 볼 수 있습니다. 스택을 사용하여 DFS를 구현할 경우에는 BFS때와 달리 그래프를 반대로 정렬해야 한다는 것이 이러한 이유 때문입니다.

 

---

3. 위 과정을 최대 깊이까지 반복하여 하위 노드가 존재하지 않는 노드에 도착했다면,

위와 같이 가장 가까운 갈림길로 돌아가서 다른 방향으로 다시 탐색을 진행하게 됩니다.

 

 

 

모든 탐색이 끝난 뒤 방문이 진행된 방향을 살펴보면

깊이를 너비보다 우선하여 탐색이 진행되었음을 알 수 있습니다.

 

 

재귀에 대한 이해가 충분하다면, 위 스택을 사용해 구현한 DFS의 동작 과정을 살펴본 것만으로도 같은 동작을 재귀로 구현할 수 있을 것입니다.

 

 

만약 재귀에 대한 이해가 부족하다면 아래 포스팅을 읽어봐주시면 감사하겠습니다.

재귀 함수 (recursive function) 의 동작

 

 

여기까지 그래프 탐색 알고리즘 BFS와 DFS에 대해 살펴보았습니다. 감사합니다.

 

키 포인트

1. BFS일 경우엔 큐, DFS일 경우에는 스택에서 정점을 꺼낸다는 것은 해당 정점을 방문한다는 것을 의미

2. 방문이 종료되는, 즉, 다음 방문으로 넘어가는 시점은 현재 방문중인 정점과 연결된 모든 정점들을 큐 또는 스택에 모두 넣었을 때.