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

너비 우선 탐색 - BFS(Breadth First Search)

DFS와 같이 그래프 완전 탐색 기법 중 하나이다.

시작노드에서 출발하여 가장 가까운 노드를 먼저 방문하며 탐색하는 알고리즘이다.

 

기능	특징(구현 방법)	시간복잡도 (V: 노드 수 / E: 엣지 수)
그래프 완전 탐색	FIFO 탐색	O(V+E)
	Queue 자료구조를 이용

 

• FIFO의 특성을 갖는 선입선출 방식의 Queue 자료구조를 사용
• 탐색 시작 노드와 가까운 노드를 우선하여 탐색
  (목표노드에 도착하는 경로가 여러개 일 때 최단 경로를 보장함.

문제 유형

• ?

핵심 이론

• 한번 방문한 노드는 재방문 하지 않음 - `방문배열` 이라고 부르는 방문 여부를 체크할 배열이 필요하다
• FIFOO(선입선출)탐색 방식 - Queue 자료구조를 사용한다. 

탐색시 필요한 구성

• Queue
• 탐색순서
• 인접리스트
• 방문배열

동작 순서

1. 시작노드를 지정하고, 사용할 자료구조, 인접리스트를 초기화한다.
   1. 시작 노드를 지정
   2. 그래프를 인접리스트로 표현
   3. 방문배열을 초기화 (시작노드만 T 나머지는 F)
   4. Queue에 시작노드 삽입
2. Queue에서 노드 출력 후 해당 노드의 인접노드를 다시 Queue에 삽입한다.
   1. POP 노드 출력
   2. PEEK 인접리스트에서 꺼낸 인접노드 확인
   3. PUSH 스택에 인접노드 삽입
   4. 방문배열 체크
3. Queue 자료구조에 값이 없을 때 까지 반복한다.
   1 ~ 2 과정을 스택에 값이 더이상 없을 때 까지 반복 (이미 다녀간 노드는 방문 배열을 바탕으로 재삽입 하지 않는것이 핵심)
   스택에 값이 없다는 의미는 시작점 기준 DFS 탐색시 더이상 갈 수 있는곳이 없음을 뜻한다. (BFS 종료)
   
   
   

---

전체 탐색 순서

 

 

[그래프]

1 → 2 → 5 ↓         ↘ 3 → 4 → 6

 

[인접리스트]

1 → 2, 3 2 → 5, 6 3 → 4 4 → 6 5  6

 

[방문 배열]

1	2	3	4	5	6
T	F	F	F	F	F

 

[Queue 입출력 순서]

		3	5
시작노드	2	5	6	6
1	3	6	4	4	4	6

 

---

 

[Queue데이터 삽입/삭제 순서]

• Queue 첫번째 데이터 1 기준
  
  1. Queue에 시작노드 1 출력
  2. 탐색 순서에 1 작성
  3. 방문 배열에 '방문 T' 체크
  4. 인접리스트 인접 노드 2,3 방문배열 방문여부 확인
  5. 2, 3 모두 F이므로 순차적으로 Queue에 삽입
     (2, 3 순차적으로 삽입 - 3, 2)
• Queue 첫번째 데이터 2 기준
  1. Queue 첫번째 노드 2 출력
  2. 탐색 순서에 2 작성
  3. 방문 배열에 '방문 T' 체크
  4. 인접리스트 인접 노드 5, 6 방문배열 방문여부 확인
  5. 방문여부 F이므로 Queue에 5, 6 삽입
     (2 제거 후 5, 6 삽입 - 6, 5, 3)
• Queue 첫번째 데이터 3 기준
  
  1. Queue 첫번째 노드 3 출력
  2. 탐색 순서에 3 작성
  3. 방문 배열에 '방문 T' 체크
  4. 인접리스트 인접 노드 4 방문배열 방문여부 확인
  5. 방문여부 F이므로 스택에 4 삽입
     (3 제거 후 4 삽입 - 4, 6, 5)

• Queue 첫번째 데이터 5 기준
  
  1. Queue 첫번째 노드 5 출력
  2. 탐색 순서에 5 작성
  3. 방문 배열에 '방문 T' 체크
  4. 인접리스트 인접 노드 없으므로 인접노드 방문여부 및 삽입 생략
     (5 제거 - 4, 6)
• Queue 첫번째  데이터 6 기준
  
  1. Queue 첫번째 노드 6 출력
  2. 탐색 순서에 6 작성
  3. 방문 배열에 '방문 T' 체크
  4. 인접리스트 인접 노드 없으므로 인접노드 방문여부 및 삽입 생략 
     (6 제거 - 4)

마지막 데이터 4 기준 

1. Queue 첫번째 노드 4 출력
2. 탐색 순서에 4 작성
3. 방문 배열에 '방문 T' 체크
4. 인접리스트 인접 노드 6은 이미 직전에 방문 했으므로 더이상 진행하지 않고 종료 (방문배열에 T 처리되어있음)
   (4제거 - 탐색종료)

<탐색 순서 결과>

1 → 2  → 3 → 5 → 6 → 4