위상 정렬은 방향 비순환 그래프에서 진입 차수가 0인 노드를 큐에 넣습니다. 하나를 꺼내 결과에 추가하고, 나가는 간선을 지워 새로 진입 차수가 0이 된 이웃을 큐에 넣습니다.
모든 노드를 꺼낼 수 없으면 순환 의존성이 있다는 뜻입니다. 선택 가능한 노드가 여러 개면 유효한 순서도 여러 개일 수 있습니다.
언제 쓰나
빌드 단계, 과목 선수 조건, 작업 의존성의 실행 순서를 정할 때 씁니다.
위상 정렬
Topological sort
의존 간선이 없는 노드부터 꺼내 선행 작업 순서를 만듭니다.
···
<div class="v"><header><b>DEPENDENCY ORDER</b><span id="state"></span></header><main><div class="tgraph" id="tgraph"></div><div class="tqueue" id="tqueue"></div></main><footer>remove zero-indegree nodes</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} .tgraph{height:65%;display:flex;align-items:center;justify-content:center;gap:clamp(4px,1.5vw,16px)}.tparallel{display:flex;flex-direction:column;gap:3px}.tgraph b{min-width:clamp(25px,7vmin,40px);height:clamp(20px,5vmin,33px);border:1px solid var(--line);border-radius:5px;display:grid;place-items:center;font:700 .8em ui-monospace,monospace}.tgraph i{width:clamp(8px,2vw,24px);height:2px;background:var(--line)}.tqueue{text-align:center;color:var(--accent);font:600 .76em ui-monospace,monospace}const order=["A","B","C","D"],ready=["B","C","D","none"];let step=0;function node(n){const i=order.indexOf(n);return "<b class='"+(i===step?"active":i<step?"muted":"")+"'>"+n+"</b>"}function draw(){document.getElementById("tgraph").innerHTML="<div class=tparallel>"+node("A")+node("B")+"</div><i></i>"+node("C")+"<i></i>"+node("D");document.getElementById("tqueue").textContent="output: "+order.slice(0,step+1).join(" → ");document.getElementById("state").textContent="next ready: "+ready[step];step=(step+1)%4}draw();setInterval(draw,900)