Pular para o conteúdo
</> Entendendo Algoritmos

Ordenação topológica

Quando as tarefas dependem umas das outras, uma ordenação topológica é uma ordem em que cada tarefa vem depois de todas as suas dependências. O algoritmo repete: faça uma tarefa que não espera por mais nada e libere as que dependiam dela. Só existe se o grafo não tiver ciclos.

Explicação do algoritmo: escolha um nível para ler.

{ }Ver o código
// grafo[a] = tarefas que só podem começar depois de a
function ordenacaoTopologica(grafo) {
  const tarefas = Object.keys(grafo);
  const faltam = {};   // quantas dependências ainda faltam para cada tarefa
  for (const t of tarefas) faltam[t] = 0;
  for (const t of tarefas) for (const d of grafo[t]) faltam[d]++;

  const fila = tarefas.filter((t) => faltam[t] === 0);   // já estão livres
  const ordem = [];

  while (fila.length > 0) {
    const atual = fila.shift();
    ordem.push(atual);

    for (const d of grafo[atual]) {
      faltam[d]--;
      if (faltam[d] === 0) fila.push(d);   // ficou livre
    }
  }

  return ordem.length === tarefas.length ? ordem : null;   // null: há ciclo
}
Tarefa feita agoraJá na ordemLivre (na fila)Presa em ciclo
acordarexercitarescovar dentesfazer lanchetomar banhovestirsair

Arraste para os lados para ver o gráfico inteiro.