Topologisch sorteren

Elke keer dat je software installeert, een programma bouwt of een project plant, moet iets uitzoeken wat eerst moet. Als taak B taak A nodig heeft, moet A eerder komen. Topologisch sorteren maakt van een web van zulke regels één rechte lijn.

Een graaf met knopen verbonden door eenrichtingspijlen, de geplaatste knopen in het groen, en daaronder de volgorde tot nu toe als rij
Een graaf met knopen verbonden door eenrichtingspijlen, de geplaatste knopen in het groen, en daaronder de volgorde tot nu toe als rij

Het idee

Teken elke taak als een knoop en elke regel "A voor B" als een pijl van A naar B. Een topologische volgorde is een rij van alle knopen waarin elke pijl naar rechts wijst. Het heet sorteren omdat het dingen op volgorde zet, maar anders dan bij het sorteren van getallen hoeft het alleen de pijlen te respecteren: knopen die geen keten van pijlen verbindt, mogen in elke volgorde komen.

Wanneer het onmogelijk is

Als de pijlen een cyclus vormen, zeg A voor B, B voor C en C voor A, dan zou A voor zichzelf moeten komen. Een topologische volgorde bestaat dus precies als de graaf geen gerichte cyclus heeft. Zo'n graaf heet een gerichte acyclische graaf, of DAG. Beide methoden hieronder vinden een cyclus als die er is, dus ze zijn ook een handige cyclustest.

Een voorbeeld

Neem de pijlen A → C, B → C, B → D, C → E en D → E. Het algoritme van Kahn telt de inkomende pijlen: A en B hebben er geen, dus A gaat eerst, dan B. Het weghalen van de pijlen van B maakt C en D vrij, die volgen, en dan E: de volgorde A, B, C, D, E. De DFS-methode bezoekt A, dan C, dan E; E is als eerste afgerond, dan C, dan A, en elk gaat vooraan. Dan bezoekt ze B en D, die daarvoor afgerond worden: de volgorde B, D, A, C, E. Beide volgordes kloppen.

Kahn of DFS?

Het algoritme van Kahn, in 1962 gepubliceerd door Arthur Kahn, werkt vooruit: het weet altijd welke taken nu kunnen beginnen, wat goed past bij planning, en het kan tussen vrije taken kiezen volgens elke regel, zoals alfabetische volgorde. De DFS-methode, populair gemaakt door Robert Tarjan in 1976, werkt achteruit vanaf de eindpunten en heeft alleen diepte-eerst zoeken nodig. Bij beide groeit de tijd met het aantal knopen plus kanten.

Robert Tarjan, die in 1972–73 met John Hopcroft aantoonde dat diepte-eerst zoeken veel graafproblemen in lineaire tijd oplost; ze kregen de Turing Award van 1986 deels voor dat werk.
Robert Tarjan, die in 1972–73 met John Hopcroft aantoonde dat diepte-eerst zoeken veel graafproblemen in lineaire tijd oplost; ze kregen de Turing Award van 1986 deels voor dat werk.

Toepassingen

Buildtools zoals make compileren bestanden na de bestanden waarvan ze afhangen. Pakketbeheerders installeren bibliotheken in volgorde van afhankelijkheid. Spreadsheets herberekenen een cel na de cellen die de formule gebruikt. Universiteiten controleren of aan de vereiste voorkennis van vakken voldaan kan worden, compilers ordenen instructies, en datapijplijnen voeren elke stap uit zodra de invoer klaar is. Het Unix-commando tsort doet zelf een topologische sortering.

Probeer het zelf

Open de app en druk op Stap. De pijlen zeggen welke knoop voor welke moet komen. Bij het algoritme van Kahn telt het getal op elke knoop de overgebleven inkomende pijlen, en vrije knopen zijn blauw. Bij de DFS-methode worden blauwe knopen nog bezocht en zijn groene geplaatst. De volgorde groeit in de rij onder de graaf. Vink Cyclus toevoegen aan en zie hoe beide methoden ontdekken dat er geen volgorde bestaat.

Veelgestelde vragen

Wat betekent topologisch hier?

De naam komt van topologie, de studie van hoe dingen verbonden zijn in plaats van hun precieze vorm. De volgorde hangt alleen af van welke knopen met pijlen verbonden zijn, niet van waar ze getekend zijn.

Hoe vind ik de cyclus als er geen volgorde is?

De DFS-methode toont die direct: de kant naar een knoop die nog bezocht wordt, samen met het pad van knopen die bezocht worden, is de cyclus. Het algoritme van Kahn vertelt alleen welke knopen vastzitten; zoeken tussen die knopen vindt de cyclus.

Kan ik een bepaalde volgorde kiezen uit de geldige?

Ja. Kies bij het algoritme van Kahn, als meerdere knopen vrij zijn, de knoop die je het liefst wilt, bijvoorbeeld de kleinste letter of de dringendste taak. Met een prioriteitswachtrij krijg je de volgorde die alfabetisch eerst komt.

Hoe wordt topologisch sorteren gebruikt bij kortste paden?

In een gerichte acyclische graaf vind je alle kortste paden vanaf een start in één doorgang: werk de afstanden bij via de kanten van elke knoop in topologische volgorde. Dat werkt zelfs met negatieve kanten, en is sneller dan Dijkstra of Bellman–Ford.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Probeer topologisch sorteren