Topologisk sortering
Varje gång du installerar programvara, bygger ett program eller planerar ett projekt måste något räkna ut vad som ska göras först. Om uppgift B behöver uppgift A måste A komma tidigare. En topologisk sortering gör ett nät av sådana regler till en rak linje.
Idén
Rita varje uppgift som en nod och varje regel "A före B" som en pil från A till B. En topologisk ordning är en rad av alla noder där varje pil pekar åt höger. Den kallas sortering eftersom den ställer saker i ordning, men till skillnad från att sortera tal behöver den bara respektera pilarna: noder som ingen kedja av pilar förbinder får komma i vilken ordning som helst.
När det är omöjligt
Om pilarna bildar en cykel, till exempel A före B, B före C och C före A, skulle A behöva komma före sig själv. En topologisk ordning finns alltså precis när grafen saknar riktad cykel. En sådan graf kallas en riktad acyklisk graf, eller DAG. Båda metoderna nedan hittar en cykel om det finns en, så de fungerar också som ett smidigt cykeltest.
Ett exempel
Ta pilarna A → C, B → C, B → D, C → E och D → E. Kahns algoritm räknar ingående pilar: A och B har inga, så A kommer först, sedan B. När B:s pilar tas bort blir C och D fria och följer efter, och sedan E: ordningen A, B, C, D, E. DFS-metoden besöker A, sedan C, sedan E; E blir färdig först, sedan C, sedan A, och var och en sätts längst fram. Sedan besöker den B och D, som blir färdiga framför dem: ordningen B, D, A, C, E. Båda ordningarna är rätt.
Kahn eller DFS?
Kahns algoritm, publicerad av Arthur Kahn 1962, arbetar framåt: den vet alltid vilka uppgifter som kan börja nu, vilket passar schemaläggning, och den kan välja bland fria uppgifter efter vilken regel som helst, till exempel bokstavsordning. DFS-metoden, populariserad av Robert Tarjan 1976, arbetar bakåt från ändarna och behöver bara en djupet-först-sökning. Båda tar tid som växer med antalet noder plus kanter.
Användning
Byggverktyg som make kompilerar filer efter filerna de beror på. Pakethanterare installerar bibliotek i beroendeordning. Kalkylblad räknar om en cell efter cellerna som dess formel använder. Universitet kontrollerar att förkunskapskraven för kurser går att uppfylla, kompilatorer ordnar instruktioner, och datapipelines kör varje steg när dess indata är klara. Unix-kommandot tsort gör en topologisk sortering på egen hand.
Utforska
Öppna appen och tryck på Steg. Pilarna säger vilken nod som måste komma före vilken. Med Kahns algoritm räknar talet på varje nod dess återstående ingående pilar, och fria noder är blå. Med DFS-metoden besöks de blå noderna, och de gröna är placerade. Ordningen växer i raden under grafen. Kryssa i Lägg till en cykel och se båda metoderna upptäcka att det inte finns någon ordning.
Ofta ställda frågor
Vad betyder topologisk här?
Namnet kommer från topologi, läran om hur saker hänger ihop snarare än deras exakta form. Ordningen beror bara på vilka noder som är förbundna med pilar, inte på var de är ritade.
Hur hittar jag cykeln när det inte finns någon ordning?
DFS-metoden visar den direkt: kanten till en nod som fortfarande besöks, tillsammans med vägen av noder som besöks, är cykeln. Kahns algoritm visar bara vilka noder som har fastnat; en sökning bland dem hittar cykeln.
Kan jag välja en viss ordning bland de giltiga?
Ja. När flera noder är fria i Kahns algoritm väljer du den du föredrar, till exempel minsta bokstaven eller den mest brådskande uppgiften. Med en prioritetskö får du den ordning som kommer först i bokstavsordning.
Hur används topologisk sortering för kortaste vägar?
I en riktad acyklisk graf hittar du alla kortaste vägar från en start i ett enda svep genom att uppdatera avstånden längs varje nods kanter i topologisk ordning, även med negativa kanter, och snabbare än Dijkstra eller Bellman–Ford.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Prova topologisk sortering