깊이 우선 탐색은 시작 노드에서 아직 방문하지 않은 이웃으로 계속 내려갑니다. 더 갈 곳이 없으면 호출 스택이나 명시적 스택을 따라 직전 갈림길로 돌아옵니다.
방문 집합을 두지 않으면 순환 그래프에서 같은 노드를 반복할 수 있습니다. 너비 우선 탐색과 달리 가중치 없는 그래프의 최단 간선 경로를 바로 보장하지는 않습니다.
언제 쓰나
연결 요소, 순환 검사, 백트래킹 문제의 탐색 순서를 만들 때 씁니다.
깊이 우선 탐색
Depth-first search
한 갈래를 끝까지 방문한 뒤 되돌아와 다른 갈래를 탐색합니다.
···
<div class="v"><header><b>DEPTH-FIRST SEARCH</b><span id="state"></span></header><main><div class="dbranches" id="dbranches"></div><div class="dstack" id="dstack"></div></main><footer>descend → backtrack → descend</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} .dbranches{height:68%;display:flex;flex-direction:column;align-items:center;justify-content:center;gap:4px}.drow{display:flex;align-items:center;justify-content:center;gap:clamp(4px,2vw,15px)}.drow b{width:clamp(22px,6vmin,40px);height:clamp(22px,6vmin,40px);border:1px solid var(--line);border-radius:50%;display:grid;place-items:center;font:700 .8em ui-monospace,monospace}.drow i{width:clamp(8px,2vw,22px);height:2px;background:var(--line)}.dstack{text-align:center;color:var(--accent);font:600 .78em ui-monospace,monospace}const stages=[{at:"A",stack:"A"},{at:"B",stack:"A → B"},{at:"D",stack:"A → B → D"},{at:"C",stack:"A → C"},{at:"E",stack:"A → C → E"}];let step=0;function row(names,at,visited){return "<div class=drow>"+names.map((v,i)=>"<b class='"+(v===at?"active":visited.includes(v)?"muted":"")+"'>"+v+"</b>"+(i<2?"<i></i>":"")).join("")+"</div>"}function draw(){const s=stages[step],visited=stages.slice(0,step).map(x=>x.at);document.getElementById("dbranches").innerHTML=row(["A","B","D"],s.at,visited)+row(["A","C","E"],s.at,visited);document.getElementById("dstack").textContent="stack: "+s.stack;document.getElementById("state").textContent=step===3?"backtrack":"visit "+s.at;step=(step+1)%stages.length}draw();setInterval(draw,900)