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
Arraste para os lados para ver o gráfico inteiro.