Pseudo Code

Lektion 4 von 9 im Kurs Topologische Sortierung - Graph-Algorithmen von 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] zählt eingehende Kanten. Nur Kanten u -> v erhöhen indeg[v].
Das Durchsuchen der Knoten 0..n-1 und das Auswählen des ersten mit In-Degree 0 ergibt bei jedem Schritt die kleinste Wahl, daher ist die Reihenfolge deterministisch.
Das Setzen von indeg[pick] = -1 ist eine einfache Methode, um einen Knoten als bereits platziert zu markieren.

Probier es selbst

Diese Lektion enthält keine Programmieraufgabe.

Teste dich selbst

Diese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.

Alle Lektionen in Topologische Sortierung - Graph-Algorithmen

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