자료구조 - 그래프 탐색 BFS 그림으로 쉽게 이해하기

자료구조 - 그래프 탐색 BFS 그림으로 쉽게 이해하기

 

안녕하세요.

로스윗의 코딩캠프입니다.

오늘은 많은 사람들이 궁금해하시고 많이들 헷갈려하시는 내용을 바탕으로

자료구조 - 그래프 탐색 BFS 그림으로 쉽게 이해하기에 대해서 같이 알아보겠습니다.

그림으로 쉽게 이해할 수 있으니 끝까지 잘 따라와주세요 :)

바로 시작하겠습니다.

 

 

 

 

 

- 그래프 탐색 BFS

이번 포스팅에서는 그래프의 탐색 방법 중 하나인 BFS에 대해서 알아보겠습니다.
BFS는 Breath-First Search의 약자로 한글로 번역하면 너비우선탐색 이라고 합니다. 너비우선이라는 것은 간단하게 말씀드리면 가까운 곳부터 탐색하는 탐색방법이라고 보시면 됩니다. 그래서 BFS는 그래프에 있어서 가까운 곳부터 너비를 먼저 탐색을 한다는 것인데 트리도 일종의 그래프라고 말씀을 드린 것을 기억하실거에요. 그리고 사실 우리는 트리를 BFS로 탐색하는 것을 이미 한 번 했었습니다. 

 

 

프린트 매서드

 

프린트 트리의 매쏘드를 다시 한 번 보도록 하겠습니다.
프린트 트리 매쏘드는 각 트리를 리벨별로 라인에 출력을 해주는 매쏘드였어요. 제일 먼저 우리가 큐를 생성해주고 큐에 트리의 루트 노드를 먼저 삽입한 다음에 while문에 진입을 했었죠. 큐는 선입선출의 구조라는 것도 기억하실거에요. 그래서 이 큐가 빌때까지 큐에 있는 노드를 꺼내고 꺼낸 노드의 자식이 있다면 큐에 그 자식노드를 각각 추가해줬었습니다.

 

 

트리 모양

 

 

그래서 위와 같은 트리가 있을 때, 제일 먼저 루트노드인 3이 큐에 들어가게 될 것입니다.

 

큐에 제일 먼저 3이 추가된다

 

 

그 다음엔 큐에 들어갔던 3이 빠지게 되면서 3의 자식이었던 6과 2가 큐에 들어가게 되겠죠.

 

 

다음으로 3이 빠지고 3의 자식이었던 6과 2가 큐에 들어간 모습

 

 

그리고 while문이 한 턴이 종료되면서 while문이 다시 위로 올라가 큐에 맨 앞에 있는 것을 하나 빼오게 되겠죠. 그러면 6을 빼오고, 6의 자식이었던 1과 4가 추가 될 것입니다.

 

 

6의 자식이었던 1과 4가 추가된 모습

 

 

그 다음에는 2가 빠지게 되면서 2의 자식이었던 5와 7일 들어가게 되겠죠.

 

 

2가 빠지게 되면서 2의 자식이었던 5와 7일 들어간 모습

 

 

- BFS의 특징

그 후에도 큐에있는 노드들이 앞에서 부터 하나씩 빠지게 되겠지만 그때는 더 이상 자식노드가 없기 때문에 큐에는 더 이상 노드가 추가되지 않고 빠지기만 하겠죠. 그러면 마지막으로 제일 늦게 삽입되었떤 7노드가 빠지게 되면 큐가 비게되면서 while문이 종료가 되게 됩니다. 이것이 트리를 BFS 즉, 너비우선탐색으로 탐색을 한 방법이 되겠습니다. BFS방법으로 탐색할 때 큐를 사용했는데요. 이렇게 BFS는 큐를 사용한다는 특징이 있습니다.

 

그럼 이번에는 큐를 써서 트리가 아닌 그래프를 BFS로 방문하게 될 때는 어떤 순서로 방문하게 되는지 알아보겠습니다.

 

반응형

 

그래프 예시

 

위 그래프를 예시로 들어보겠습니다. 우선 시작점을 A로 잡으면 A가 먼저 큐에 들어갑니다.

 

 

A가 먼저 큐에 들어간 모습

 

 

그럼 이 상태에서 while문에 진입을 해서 큐에 있는 노드들을 하나씩 빼오면서 자식노드들을 추가하겠죠. 여기서도 비슷한 매커니즘으로 가게 됩니다. 우선 큐에 있는 A노드를 가져오면서 A노드를 먼저 방문을 하게 되고, 그 후에 A에 연결된 노드들을 탐색을 합니다. 여기서는 연결된 노드가 B 하나밖에 없기 때문에 B노드를 큐에 삽입을 하게 됩니다.

 

 

A노드를 빼오고 B노드를 삽입한 모습

 

 

그 다음에도 마찬가지로 큐에 들어있는 B를 가져오면서 B를 방문합니다. 그리고 B에 연결된 노드들을 탐색을 했을 때 C, D, E가 있습니다. 그래서 이 C, D, E를 큐에다가 각각 삽입을 해줍니다. 그러면 현재까지 방문한 노드는 A와 B가 됩니다.

 

 

B를 빼오고 큐에 C, D, E가 각각 삽입된 모습

 

 

그 다음으로 이번에는 큐에서 가장 앞에 있는 C를 빼면서 C를 방문하게 됩니다. 그리고 C와 연결된 노드들을 탐색을 하는데, C와 연결된 노드들을 보면 B, D, F가 있는 것을 확인 할 수 있습니다. 근데 B는 이미 방문한 노드이고, D는 큐에 이미 들어있기 때문에 B와 D를 제외하고 F만 큐에 삽입을 해줍니다. 그러면 현재까지 방문한 노드는 A - B - C 순서가 되겠죠.

 

 

F만 큐에 삽입한 모습

 

그 다음으로 큐에 맨 앞에 있는 D노드가 빠지게 되면서 D노드를 방문합니다. 그리고 D에 연결된 노드를 탐색을 하는데, 연결된 노드들을 보면 총 5개나 됩니다. B, C, E, G, H가 모두 D에 연결되어 있는 vertex이지만 여기서도 이미 방문을 했거나 이미 큐에 삽입이 된 노드들은 큐에 삽입을 하지 않습니다. 그렇기 때문에 이때 큐에 삽입 될 노드들은 G와 H노드 뿐입니다. 그러면 현재까지 방문한 노드 순서는 A - B - C - D 순서가 됩니다.

 

 

D노드가 빠지고 G, H노드가 삽입된 모습

 

 

그 다음으로 큐에 맨앞에 있는 E노드를 빼오면서 방문을 하게 됩니다. 이제는 계속해서 큐에 남아있는 노드들을 앞에서부터 하나씩 빼오는데 더이상 큐에 삽입 될 노드가 없기 때문에 E, F, G, H를 방문하면서 큐가 비게되고, BFS탐색이 종료가 되게 됩니다. 그래서 최종적으로 위와같은 트리에서 BFS탐색을 할 경우 노드 방문 순서는 A - B - C - D - E - F - G - H가 됩니다. 

 

오늘은 이렇게 자료구조 - 그래프 탐색 BFS 그림으로 쉽게 이해하기에 대해서 알아보았습니다.

다음 시간에는 그래프 탐색 DFS에 대해서 알아보겠습니다.

감사합니다.