Pseudo Code

Leçon 4 sur 9 du cours Tri topologique - Algorithmes de graphes de 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] compte les arêtes entrantes. Seules les arêtes u -> v s'ajoutent à indeg[v].
Parcourir les sommets 0..n-1 et prendre le premier ayant un degré entrant de 0 donne le plus petit choix à chaque étape, l'ordre est donc déterministe.
Définir indeg[pick] = -1 est un moyen simple de marquer un sommet comme déjà placé.

Essayez vous-même

Cette leçon ne comprend pas de défi de code.

Testez-vous

Cette leçon comprend un petit quiz. Commencez la leçon pour y répondre et suivre votre progression.

Toutes les leçons de Tri topologique - Algorithmes de graphes

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