728x90
https://www.youtube.com/watch?v=CJiF-muKz30&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=19
BFS (Breadth-First Search)
-
BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다
-
BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다
-
[Step 0] 그래프를 준비한다 (방문 기준: 번호가 낮은 인접 노드부터)
- 시작 노드: 1
- [Step 1] 시작 노드인 '1'을 큐에 삽입하고 방문 처리를 한다
- [Step 2] 큐에서 노드 '1'을 꺼내 방문하지 않은 인접 노드 '2', '3', '8'을 큐에 삽입하고 방문 처리한다
- [Step 3] 큐에서 노드 '2'를 꺼내 방문하지 않은 인접 노드 '7'을 큐에 삽입하고 방문 처리한다
- [Step 4] 큐에서 노드 '3'을 꺼내 방문하지 않은 인접 노드 '4', '5'를 큐에 삽입하고 방문 처리한다
- [Step 5] 큐에서 노드 '8'을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시한다
- 이러한 과정을 반복하여 전체 노드의 탐색 순서(큐에 들어간 순서)는 다음과 같다
BFS 소스코드 예제 (Python)
from collections import deque
# BFS 함수 정의
def bfs(graph, start, visited):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque([start])
# 현재 노드를 방문 처리
visited[start] = True
# 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 뽑아 출력
v = queue.popleft()
print(v, end=' ')
# 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
# 정의된 BFS 함수 호출
bfs(graph, 1, visited)
실행 결과
1 2 3 8 7 4 5 6
BFS 소스코드 예제 (Java)
import java.util.*;
public class Main {
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
// BFS 함수 정의
public static void bfs(int start) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
// 현재 노드를 방문 처리
visited[start] = true;
// 큐가 빌 때까지 반복
while(!q.isEmpty()) {
// 큐에서 하나의 원소를 뽑아 출력
int x = q.poll();
System.out.print(x + " ");
// 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for(int i = 0; i < graph.get(x).size(); i++) {
int y = graph.get(x).get(i);
if(!visited[y]) {
q.offer(y);
visited[y] = true;
}
}
}
}
public static void main(String[] args) {
// 그래프 초기화
for (int i = 0; i < 9; i++) {
graph.add(new ArrayList<Integer>());
}
// 노드 1에 연결된 노드 정보 저장
graph.get(1).add(2);
graph.get(1).add(3);
graph.get(1).add(8);
// 노드 2에 연결된 노드 정보 저장
graph.get(2).add(1);
graph.get(2).add(7);
// 노드 3에 연결된 노드 정보 저장
graph.get(3).add(1);
graph.get(3).add(4);
graph.get(3).add(5);
// 노드 4에 연결된 노드 정보 저장
graph.get(4).add(3);
graph.get(4).add(5);
// 노드 5에 연결된 노드 정보 저장
graph.get(5).add(3);
graph.get(5).add(4);
// 노드 6에 연결된 노드 정보 저장
graph.get(6).add(7);
// 노드 7에 연결된 노드 정보 저장
graph.get(7).add(2);
graph.get(7).add(6);
graph.get(7).add(8);
// 노드 8에 연결된 노드 정보 저장
graph.get(8).add(1);
graph.get(8).add(7);
bfs(1);
}
}
실행 결과
1 2 3 8 7 4 5 6
728x90
'CodingTest' 카테고리의 다른 글
[이것이 코딩 테스트다 with Python] 21강 선택 정렬 (0) | 2021.01.04 |
---|---|
[이것이 코딩 테스트다 with Python] 20강 DFS & BFS 기초 문제 풀이 (0) | 2021.01.04 |
[이것이 코딩 테스트다 with Python] 18강 DFS 알고리즘 (0) | 2021.01.04 |
[이것이 코딩 테스트다 with Python] 17강 재귀 함수 (0) | 2021.01.04 |
[이것이 코딩 테스트다 with Python] 16강 스택과 큐 자료구조 (0) | 2021.01.04 |
댓글