[알고리즘] 너비 우선 탐색 (BFS, Breadth First Search)

그래프 탐색 알고리즘 중 하나이다.

그래프?

[자료구조] 그래프와 트리

[자료구조] 그래프를 코드로 나타내는 방법 (feat. C++)

너비 우선 탐색(BFS)?

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법.

 

현재 노드에서 모든 인접 노드를 탐색하고 나서 그 다음 아래 계층으로 내려간다.

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것.

너비 우선 탐색(BFS)을 사용하는 경우

최단거리를 구할 때 쓰기 좋다. 탐색 과정에서 최초로 목표 노드에 도달했을 때가 최단거리임이 보장되기 때문이다.

물론 임의의 경로를 찾고 싶을 때도 사용 가능하다.

너비 우선 탐색(BFS)의 특징

➤ BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
즉, 선입선출(FIFO) 원칙으로 탐색. 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.
큐가 비거나 정답이 되는 노드를 찾기 전까지 계속 큐에서 노드를 하나 빼서 다음 갈 수 있는 노드를 큐에 넣는 것을 반복한다.

 

➤ 직관적이지 않은 면이 있다.

➤ BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.

➤ 구현할 때 주의할 점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것.

(이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.)

➤ ‘Prim’, ‘Dijkstra’ 알고리즘과 유사하다.

너비 우선 탐색(BFS)의 과정

1. 큐에 방문할 노드를 삽입(enqueue)한다.
   - 초기 상태의 큐에는 시작 노드만이 저장됨.
   - 처음 이후 부터는, 꺼낸 노드에 인접한, 아래 계층의 노드들을 큐에 삽입.
   - 인접한 아래 계층의 노드가 없으면 skip.
2. 노드 방문. (큐에서 노드를 꺼내고, 방문 체크한다.) (dequeue)
   - 큐에서 꺼낸 노드와 같은 계층의 노드들부터 방문.
   - 더 이상 해당 계층에 방문 안 한 노드가 없다면, 다음 계층의 노드를 방문. (큐의 앞에서 노드를 꺼낸다.)

큐가 소진될 때까지 계속한다.

 

 1. 큐에 처음 방문할 시작 노드를 삽입. (1️⃣)

 큐    1️⃣

 방문

 

---

 

 2. 노드 방문. (1️⃣)

 큐    
 방문 1️⃣

 

---

 

 1.  방문한 노드에 인접한 다음 계층의 노드들을 큐에 추가. (2️⃣ 3️⃣)

 큐    2️⃣ 3️⃣
 방문 1️⃣

  

---

 

 2. 다음 계층 노드 방문. (2️⃣)

 큐    3️⃣
 방문 1️⃣ 2️⃣

 

---

 

 1. 방문한 노드에 인접한 다음 계층의 노드들을 큐에 추가. (4️⃣ 5️⃣)

 큐    3️⃣ 4️⃣ 5️⃣
 방문 1️⃣ 2️⃣

 

---

 

 2. 노드 방문. (3️⃣)

 큐    4️⃣ 5️⃣
 방문 1️⃣ 2️⃣ 3️⃣

 

---

 

 1. 방문한 노드에 인접한 다음 계층의 노드들을 큐에 추가. (6️⃣ 7️⃣)

 큐    4️⃣ 5️⃣ 6️⃣ 7️⃣
 방문 1️⃣ 2️⃣ 3️⃣

 

---

 

 2. 다음 계층 노드 방문. (4️⃣)

 큐    5️⃣ 6️⃣ 7️⃣
 방문 1️⃣ 2️⃣ 3️⃣ 4️⃣

 

---

 

 1. 방문한 노드에 인접한 다음 계층의 노드들을 큐에 추가. (8️⃣)

 큐    5️⃣ 6️⃣ 7️⃣ 8️⃣
 방문 1️⃣ 2️⃣ 3️⃣ 4️⃣

 

---

 

 2. 노드 방문. (5️⃣)

 큐    6️⃣ 7️⃣ 8️⃣
 방문 1️⃣ 2️⃣ 3️⃣ 4️⃣ 5️⃣

 

---

 

 1. 방문한 노드에 인접한 다음 계층의 노드들을 큐에 추가. (9️⃣)

 큐    6️⃣ 7️⃣ 8️⃣ 9️⃣
 방문 1️⃣ 2️⃣ 3️⃣ 4️⃣ 5️⃣

 

---

 

 2. 노드 방문. (6️⃣)

 큐    7️⃣ 8️⃣ 9️⃣
 방문 1️⃣ 2️⃣ 3️⃣ 4️⃣ 5️⃣ 6️⃣

 

---

 

 1. 큐에 추가할 노드 없음 (skip)
 2. 노드 방문. (7️⃣)

 큐    8️⃣ 9️⃣
 방문 1️⃣ 2️⃣ 3️⃣ 4️⃣ 5️⃣ 6️⃣ 7️⃣

---

 

 1. 큐에 추가할 노드 없음 (skip)
 2. 다음 계층 노드 방문. (8️⃣)

 큐    9️⃣
 방문 1️⃣ 2️⃣ 3️⃣ 4️⃣ 5️⃣ 6️⃣ 7️⃣ 8️⃣

---

 

 1. 큐에 추가할 노드 없음 (skip)
 2. 다음 계층 노드 방문. (9️⃣)

 큐    
 방문 1️⃣ 2️⃣ 3️⃣ 4️⃣ 5️⃣ 6️⃣ 7️⃣ 8️⃣ 9️⃣

---

References

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

https://velog.io/@polynomeer/너비-우선-탐색BFS

https://hongku.tistory.com/156?category=804730

 

 

 

 

 

 

 

 

TRANSLATE with x

English

Arabic	Hebrew	Polish
Bulgarian	Hindi	Portuguese
Catalan	Hmong Daw	Romanian
Chinese Simplified	Hungarian	Russian
Chinese Traditional	Indonesian	Slovak
Czech	Italian	Slovenian
Danish	Japanese	Spanish
Dutch	Klingon	Swedish
English	Korean	Thai
Estonian	Latvian	Turkish
Finnish	Lithuanian	Ukrainian
French	Malay	Urdu
German	Maltese	Vietnamese
Greek	Norwegian	Welsh
Haitian Creole	Persian

 

TRANSLATE with

COPY THE URL BELOW

Back

EMBED THE SNIPPET BELOW IN YOUR SITE

Enable collaborative features and customize widget: Bing Webmaster Portal

Back