너비 우선 탐색은 시작 노드를 큐에 넣고, 앞에서 하나씩 꺼내며 아직 방문하지 않은 이웃을 뒤에 넣습니다. 같은 거리의 노드를 먼저 처리한 뒤 다음 거리로 넘어갑니다.
가중치가 없는 그래프에서는 처음 도착한 경로가 간선 수 기준 최단 경로입니다. 방문 표시가 없으면 순환 그래프에서 같은 노드를 반복 처리할 수 있습니다.
언제 쓰나
최단 단계 수를 찾거나 연결된 노드를 거리별로 펼칠 때 씁니다.
너비 우선 탐색
Breadth-first search
시작점에서 가까운 노드부터 FIFO 큐 순서대로 방문합니다.
···
<div class="v"><header><b>BREADTH-FIRST SEARCH</b><span id="state"></span></header><main><div class="levels" id="levels"></div><div class="queue" id="queue"></div></main><footer>A → B,C → D,E,F</footer></div>.v{width:min(92vw,660px);height:min(86vh,310px);box-sizing:border-box;padding:clamp(9px,2.5vmin,18px);border:1px solid var(--line);border-radius:14px;background:var(--surface);display:flex;flex-direction:column;gap:7px;color:var(--fg);font:500 clamp(15px,4.5vmin,19px)/1.25 var(--font-sans, sans-serif)}.v header,.v footer{display:flex;justify-content:space-between;align-items:center;gap:8px;white-space:nowrap}.v header b{color:var(--accent);font-size:.9em}.v header span,.v footer{color:var(--muted);font-size:.82em}.v main{flex:1;min-height:0;position:relative;overflow:hidden}.v .mono{font-family:ui-monospace,SFMono-Regular,Consolas,monospace}.v .active{background:var(--accent)!important;color:var(--bg)!important;border-color:var(--accent)!important}.v .muted{opacity:.45} .levels{height:calc(100% - 24px);display:flex;justify-content:center;align-items:center;gap:7px}.level{display:flex;flex-direction:column;justify-content:center;gap:2px}.level b{width:clamp(22px,2.5vw,34px);height:clamp(22px,2.5vw,34px);border-radius:50%;border:1px solid var(--line);display:grid;place-items:center;font:700 .8em ui-monospace,monospace}.queue{position:absolute;left:0;right:0;bottom:0;height:22px;display:grid;place-items:center;text-align:center;color:var(--muted);font:600 .8em ui-monospace,monospace}let n=0;const layers=[["A"],["B","C"],["D","E","F"]];function draw(){document.getElementById("levels").innerHTML=layers.map((l,i)=>"<div class=level>"+l.map(x=>"<b class=\""+(i===n?"active":i>n?"muted":"")+"\">"+x+"</b>").join("")+"</div>").join("");document.getElementById("queue").textContent="FIFO queue: "+layers[(n+1)%3].join(" ");document.getElementById("state").textContent="distance "+n;n=(n+1)%3}draw();setInterval(draw,1000)