Pseudo Code

Lição 4 de 9 do curso Ordenação Topológica - Algoritmos de Grafos da Coddy.

topologicalSort(n, edges):
   build directed adjacency; compute indeg[v] for all v
   order = []
   repeat n times:
      pick = smallest v with indeg[v] == 0 (none left -> stop)
      mark pick as used (indeg[pick] = -1)
      order.add(pick)
      for nb in adj[pick]:
         indeg[nb] -= 1
   return order

indeg[v] conta as arestas de entrada. Apenas arestas u -> v somam ao indeg[v].
Percorrer os vértices 0..n-1 e pegar o primeiro com grau de entrada 0 fornece a menor escolha a cada passo, portanto a ordem é determinística.
Definir indeg[pick] = -1 é uma maneira simples de marcar um vértice como já posicionado.

Experimente você mesmo

Esta lição não inclui um desafio de código.

Teste seus conhecimentos

Esta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.

Todas as lições de Ordenação Topológica - Algoritmos de Grafos

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2