방문함
큐에 있음
확인한 간선

  • 현재
  • 큐에 있음
  • 방문함
  • 경로
노드 클릭으로 설정

너비 우선 탐색 자세히 알아보기

너비 우선 탐색 (BFS)

너비 우선 탐색은 그래프를 고리 모양으로 넓혀 가며 탐색합니다. 먼저 시작 노드와 이웃한 노드 전부, 그다음 간선 두 개 떨어진 노드 전부, 이런 식입니다. 이를 선입선출 큐로 해냅니다. 노드를 클릭해 그곳에서 시작하고, 원하면 목표도 고른 뒤, 탐색을 한 단계씩 진행해 보세요. 큐가 늘고 줄어드는 모습, 각 노드가 거리를 얻는 모습, 최단 경로가 나타나는 모습을 볼 수 있습니다. 재생을 눌러 탐색을 보거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 노드를 클릭하면 시작 노드가 됩니다. 클릭을 목표로 바꾸고 다른 노드를 클릭하면 그 노드까지의 최단 경로를 찾습니다. 각 노드의 숫자는 시작 노드로부터의 거리이고, 그래프 아래의 줄이 큐입니다. 새 그래프는 다른 그래프를 만듭니다. 노드와 간선 수를 고를 수 있습니다. 보드를 선택한 상태에서 화살표 키는 단계 이동, 스페이스 바는 재생과 일시 정지, Home과 End는 처음과 끝으로 이동합니다.

작동 원리

  1. 노드를 클릭해 시작 노드로 정합니다. 경로를 찾으려면 클릭을 목표로 바꾸고 다른 노드를 클릭하세요.
  2. 재생을 누르거나, 단계와 뒤로로 한 단계씩 이동하세요. 단계 슬라이더를 끌면 탐색의 원하는 곳으로 이동합니다.
  3. 그래프 아래의 큐와 각 노드의 거리를 지켜보세요. 새 그래프로 다른 그래프를 시도할 수 있습니다.

너비 우선 탐색의 원리

시작 노드를 거리 0으로 큐에 넣습니다. 그다음 반복합니다. 큐의 맨 앞 노드를 꺼내 이웃 노드를 하나씩 봅니다. 아직 보지 않은 이웃은 꺼낸 노드보다 거리가 1 크고, 꺼낸 노드를 자신에게 도달한 경로로 기억하며, 큐의 맨 뒤에 들어갑니다. 이미 본 이웃은 건너뜁니다. 큐가 비면 도달할 수 있는 모든 노드의 거리가 정해집니다.

최단 경로를 찾는 이유

큐는 노드를 발견된 순서대로 내주고, 노드는 고리 단위로 발견됩니다. 거리 1인 노드는 모두 거리 2인 어떤 노드보다도 먼저 큐에 들어가고, 이후도 마찬가지입니다. 그래서 노드에 처음 도달하는 경로는 간선 수가 가장 적습니다. 기억해 둔 노드를 목표에서 시작까지 거꾸로 따라가면 그 경로가 나옵니다. 이는 간선 수만 셉니다. 간선 길이가 서로 다르면 다익스트라 알고리즘이 필요합니다.

자주 묻는 질문

너비 우선 탐색이란 무엇인가요?

시작 노드에서 그래프를 탐색하는 방법으로, 먼저 이웃 노드를 모두 방문하고, 그다음 그 이웃의 이웃을 방문하는 식으로 고리 단위로 넓혀 갑니다. 노드를 발견된 순서대로 두기 위해 큐를 사용합니다.

너비 우선 탐색은 최단 경로를 찾나요?

네, 모든 간선의 가중치가 같다면 찾습니다. BFS가 어떤 노드에 처음 도달할 때 사용한 간선 수가 가장 적습니다. 간선 길이가 서로 다르면 다익스트라 알고리즘을 사용하세요.

BFS와 DFS의 차이는 무엇인가요?

너비 우선 탐색은 큐를 사용해 고리 단위로 고르게 퍼져 나갑니다. 깊이 우선 탐색은 스택(또는 재귀)을 사용해 한 경로를 끝까지 깊이 따라간 뒤 되돌아옵니다. BFS는 간선 수 기준 최단 경로를 찾지만 DFS는 찾지 못합니다. 대신 DFS는 사이클 찾기와 위상 정렬에 유용합니다.

너비 우선 탐색은 얼마나 빠른가요?

각 노드를 큐에서 한 번씩 꺼내고 각 간선을 양 끝에서 보므로, 작업량은 노드 수와 간선 수의 합에 비례해 늘어납니다.

내 그래프가 어딘가로 전송되나요?

아니요. 그래프는 브라우저 안에서 만들어지고 탐색되며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

편집기로 이동