Topological sort

위상 정렬

Remove nodes with no incoming edges to produce a dependency order.

···
html
<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>
css
.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}
js
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)

Topological sort starts with zero-indegree nodes in a directed acyclic graph. Removing one node from the queue emits it and lowers the indegree of its outgoing neighbors.

If nodes remain after the queue empties, the graph contains a cycle. Several valid orders can exist when multiple nodes become ready together.

When to use

Use it to order build steps, prerequisites, or dependent jobs.

Open as page ↗