Kahn's Algorithm: como eu ordenei 31 tipos de nodes sem pirar

Eu estava construindo o Study Buddy , um canvas interativo com 31 tipos de nodes (soma, multiplicação, matrizes, condicionais, loops) , e cheguei num problema: em que ordem eu computo os nodes?

Se o node A alimenta B e B alimenta C, eu preciso calcular A antes de B, e B antes de C. Parece óbvio. Mas quando você tem 50 nodes conectados de formas arbitrárias, com bifurcações e convergências, "óbvio" vira caos rápido.

A analogia: vestir roupa

Pensa assim: você não pode colocar os sapatos antes das meias. Não pode vestir o casaco antes da camisa. Existe uma ordem de dependências.

• Meias → Sapatos
• Camisa → Casaco
• Calça → Cinto

Topological sort é exatamente isso: dada uma lista de tarefas com dependências entre elas, encontrar uma ordem válida onde cada tarefa só acontece depois de suas dependências.

Agora troca "roupas" por "nodes num canvas" e "vestir" por "computar". Mesmo problema.

Onde eu encontrei o Kahn's

Eu já conhecia topological sort via DFS (o clássico de faculdade). Mas quando pesquisei formas de implementar isso com detecção de ciclos nativa e de forma mais intuitiva pra debugar, caí no paper original do Arthur B. Kahn de 1962: "Topological sorting of large networks".

O algoritmo é elegante. Em vez de recursão e backtracking (DFS), ele usa uma fila BFS. E o melhor: se sobrar nodes no final, tem ciclo. Sem precisar de visited sets, sem DFS reverso, sem nada extra.

O algoritmo: passo a passo

Dado um DAG (Directed Acyclic Graph):

1. Calcule o in-degree de cada node (quantas arestas apontam pra ele)

2. Coloque todos os nodes com in-degree 0 numa fila (eles não dependem de ninguém)

3. Enquanto a fila não estiver vazia:

• Remove um node da fila → adiciona na ordem final
• Para cada vizinho desse node: decrementa o in-degree
• Se o in-degree do vizinho chegou a 0 → adiciona na fila

4. Se a ordem final tem todos os nodes → sucesso. Se não → ciclo detectado.

Visualmente:

Grafo: A → B → D
       A → C → D

In-degrees: A=0, B=1, C=1, D=2

Passo 1: Fila = [A]          Ordem = []
Passo 2: Processa A → B(0), C(0)
         Fila = [B, C]       Ordem = [A]
Passo 3: Processa B → D(1)
         Fila = [C]          Ordem = [A, B]
Passo 4: Processa C → D(0)
         Fila = [D]          Ordem = [A, B, C]
Passo 5: Processa D
         Fila = []            Ordem = [A, B, C, D]

4 nodes processados, 4 no grafo → sem ciclos ✓

Complexidade

• Tempo: O(V + E) , visita cada node e cada aresta uma vez
• Espaço: O(V) , a fila e o array de in-degrees

Isso é linear. Não importa se você tem 10 ou 10.000 nodes, o custo escala linearmente com o tamanho do grafo.

A implementação no Study Buddy

No Study Buddy, o canvas do ReactFlow me dá nodes e edges. A engine de computação precisa processar tudo na ordem certa. Mas aqui vem o twist: eu não recomputo o grafo inteiro a cada mudança.

Propagação incremental

Quando o usuário digita num node de Input, eu não preciso recalcular todos os 50 nodes. Só preciso recalcular os descendentes do node que mudou.

O fluxo:

1. Usuário muda o node X → identifica changedIds = [X]

2. BFS forward pela adjacency list → coleta o "dirty set" (X + todos os descendentes)

3. Kahn's topological sort scoped ao dirty set (não ao grafo inteiro)

4. Recomputa apenas os nodes na ordem topológica do dirty set

// 1. Monta adjacency list (memoizada, só recalcula se edges mudam)
function buildAdjacency(edges: Edge[]): Map<string, string[]> {
  const adj = new Map<string, string[]>()
  for (const edge of edges) {
    if (!adj.has(edge.source)) adj.set(edge.source, [])
    adj.get(edge.source)!.push(edge.target)
  }
  return adj
}

// 2. BFS forward para coletar dirty set
function getDirtySet(changedIds: string[], adj: Map<string, string[]>): Set<string> {
  const dirty = new Set<string>(changedIds)
  const queue = [...changedIds]

  while (queue.length > 0) {
    const current = queue.shift()!
    const neighbors = adj.get(current) || []
    for (const neighbor of neighbors) {
      if (!dirty.has(neighbor)) {
        dirty.add(neighbor)
        queue.push(neighbor)
      }
    }
  }
  return dirty
}

// 3. Kahn's sort scoped ao dirty set
function topologicalSort(
  dirtySet: Set<string>,
  edges: Edge[]
): string[] {
  // In-degrees apenas dos nodes no dirty set
  const inDegree = new Map<string, number>()
  for (const id of dirtySet) inDegree.set(id, 0)

  for (const edge of edges) {
    if (dirtySet.has(edge.source) && dirtySet.has(edge.target)) {
      inDegree.set(edge.target, (inDegree.get(edge.target) || 0) + 1)
    }
  }

  // Fila inicial: dirty nodes com in-degree 0
  const queue: string[] = []
  for (const [id, degree] of inDegree) {
    if (degree === 0) queue.push(id)
  }

  const sorted: string[] = []
  while (queue.length > 0) {
    const current = queue.shift()!
    sorted.push(current)

    for (const edge of edges) {
      if (edge.source === current && dirtySet.has(edge.target)) {
        const newDegree = (inDegree.get(edge.target) || 1) - 1
        inDegree.set(edge.target, newDegree)
        if (newDegree === 0) queue.push(edge.target)
      }
    }
  }

  // Detecção de ciclo
  if (sorted.length !== dirtySet.size) {
    console.warn('Cycle detected in graph')
  }

  return sorted
}

O resultado

Num grafo de 50 nodes, alterar 1 input que alimenta 5 nodes recomputa apenas 5 nodes em vez de 50. Isso é a diferença entre uma UI que trava e uma que responde em tempo real enquanto o usuário digita.

Detecção de ciclos na prática

No canvas, o usuário pode conectar qualquer node a qualquer outro. Se ele cria A → B → C → A, é um ciclo. O Kahn's detecta isso naturalmente: após processar a fila, se sorted.length < dirtySet.size, tem nodes que nunca chegaram a in-degree 0 , estão presos num ciclo.

No Study Buddy, quando isso acontece, eu marco visualmente as edges envolvidas com vermelho e mostro um warning. O usuário entende imediatamente que algo está errado.

DFS vs BFS (Kahn's): por que escolhi BFS

Para o caso de uso do Study Buddy , recomputação incremental com detecção de ciclos , Kahn's foi a escolha óbvia.

TL;DR

Kahn's Algorithm é topological sort via BFS. Você conta dependências (in-degrees), processa nodes sem dependência, decrementa vizinhos, repete. Se sobrar nodes, tem ciclo.

No Study Buddy, combinei Kahn's com propagação incremental: em vez de ordenar e computar o grafo inteiro, faço BFS forward pra achar os nodes afetados e aplico Kahn's só nesse subset.

Resultado: computação em tempo real com 50+ nodes sem travar a UI.

O paper original tem 4 páginas. Às vezes a solução mais elegante já existe desde 1962.