그래프 탐색 BFS

이 글에서는 BFS에 대해서 알아보겠습니다.

그래프에서 각 정점들을 중복 없이 한 번씩 방문하는 방법입니다.

그래프 탐색에는 2가지 종류가 있는데

깊이 우선 탐색(Depth First Search)과 너비 우선 탐색(Breadth First Search)입니다.

각 줄여서 DFS, BFS라고 흔히들 부릅니다.

제목에 적혀있다시피 이번글에서는 BFS(너비 우선 탐색)를 다룰 것입니다.

너비 우선 탐색은 시작하는 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다.

말만 들어서는 이해가 쉽지 않으니 그림을 한 번 봅시다.

위의 그림이 있을 때 우선 루트에서 시작을 합니다.

그러니 제일 위쪽의 노드(근노드)가 1이 되고 이제 탐색을 시작합니다.

시작 정점으로부터 가까운 정점부터 방문을 하게 되기에 Level1 3개의 노드 중 하나로 이동할 것인데 이럴 때는 왼쪽이 우선입니다. 그러니 Level1의 왼쪽 노드를 두 번째로 방문합니다. 이제 다음에 가야 할 곳을 생각해 봅시다.

눈으로 보았을 때 다음으로 갈 수 있을 것으로 예측되는 부분은 Level1의 중간노드와 Level2의 왼쪽노드입니다.

둘 중 어디일까요?

헷갈린다면 한국어로 생각해 보죠. 너비 우선 탐색입니다. 그렇다면 넓게 탐색한다고 생각하면 좋습니다.

이런 생각을 가지고 보면 다음은 Level1의 중간 노드일 것입니다.

같은 방법으로 계속 탐색을 하면

아래 그림과 같이 탐색이 완료될 것입니다.

너비 우선 탐색이라는 이름처럼 넓게 퍼져나가듯이 탐색이 되는 것이 특징입니다.

곧 쓰겠지만 DFS도 이름처럼 깊이 탐색이 되는 것이 특징이죠.

다음은 DFS에 대해서 알아보겠습니다. 사실 이렇게 글을 쓰면서 제가 잘 쓰고 있는지 헷갈려요.

소설이나 가사 같은 건 많이 적어봤지만 이런 글을 써보는 건 익숙지 않아서 혹시나 이 글을 보시는 분 중 피드백하고 싶은 게 있다면 편하게 해 주세요. 환영합니다.

자료 도서관