너비 우선 탐색(BFS)

그래프 순회 저번에 배운 깊이 우선 탐색(Depth First Search) - 스택을 이용하여 그래프를 순회하는 방법 너비 우선 탐색(Breadth First Search) - 큐를 이용하여 그래프를 순회하는 방법 너비 우선 탐색(BFS) 인접한 노드들을 우선 모두 색칠해 두고 뻗어나간다. 위의 그림에서 너비 우선 탐색을 사용한다고 하자. 우선 1을 큐에 넣고, (1)을 제거한다. -> 현재 노드 위치 1의 인접 노드인 2와 4를 큐에 넣는다. 이후 1의 이웃한 노드들이 모두 색칠되었으므로, 큐의 제일 앞 노드를 제거한다.(2) 2가 제거되었으므로 현재 노드 위치는 2이다. 2의 인접 노드인 3을 큐에 넣는다. 4는 이미 추가되어있으므로 추가하지 않음. 2의 인접 노드가 모두 색칠되었으므로, 큐의 제일..

원문링크 : 너비 우선 탐색(BFS)