BFS란 ? (너비 우선 탐색)
그래프 혹은 트리에서 모든 노드를 한번씩 탐색하기 위한 기본적인 방법.
완전 탐색을 수행하기 위해 사용할 수 있는 방법중 하나.
(모든 간선길이가 동일할 때)최단거리를 탐색하기 위한 목적으로 사용할 수 있음.
queue 자료구조를 사용.
기본적으로
DFS - stack
BFS - queue
BFS
- 시작노드를 큐에 넣고 [방문처리]
- 큐에서 원소를 하나씩 꺼내면서 방문하지 않은 인접된 노드가 있는지 확인.
있으면 방문하지 않은 인접노드를 큐에 모두 삽입하고 방문처리.
while문으로 false가 될때까지 반복.
// 그래프를 인접 리스트로 표현하는 객체
const graph = {
A: ['B', 'C'],
B: ['A', 'D', 'E'],
C: ['A', 'F', 'G'],
D: ['B'],
E: ['B'],
F: ['C'],
G: ['C'],
};
// 방문한 노드를 저장하기 위한 Set 객체 생성
const visited = new Set();
// BFS 함수 정의
function bfs(startNode) {
// 시작 노드를 큐에 추가하고 방문 처리
const queue = [startNode];
visited.add(startNode);
// 큐가 비어있을 때까지 반복
while (queue.length > 0) {
// 큐의 맨 앞 노드를 꺼내고 인접 노드들을 확인
const currentNode = queue.shift();
console.log(currentNode);
for (const neighbor of graph[currentNode]) {
// 방문하지 않은 인접 노드라면 큐에 추가하고 방문 처리
if (!visited.has(neighbor)) {
queue.push(neighbor);
visited.add(neighbor);
}
}
}
}
// 시작 노드를 'A'로 설정하여 BFS 호출
bfs('A');
DFS 와 BFS 를 봤는데 개념적인 부분보다 문제를 많이 접해봐야 할 것 같다.
github에 알고리즘 적어두고 보기