Topologisk sortering
Hver gang du installerer software, bygger et program eller planlægger et projekt, skal noget finde ud af, hvad der skal gøres først. Kræver opgave B opgave A, skal A komme tidligere. En topologisk sortering gør et net af sådanne regler til én lige linje.
Idéen
Tegn hver opgave som en knude og hver regel "A før B" som en pil fra A til B. En topologisk rækkefølge er en række af alle knuderne, hvor hver pil peger mod højre. Den kaldes en sortering, fordi den sætter ting i rækkefølge, men i modsætning til at sortere tal skal den kun respektere pilene: knuder, som ingen kæde af pile forbinder, må komme i vilkårlig rækkefølge.
Når det er umuligt
Danner pilene en kreds, for eksempel A før B, B før C og C før A, så skulle A komme før sig selv. En topologisk rækkefølge findes altså netop, når grafen ikke har nogen orienteret kreds. Sådan en graf kaldes en orienteret acyklisk graf, eller DAG. Begge metoder nedenfor finder en kreds, hvis der er en, så de er også en praktisk kredstest.
Et eksempel
Tag pilene A → C, B → C, B → D, C → E og D → E. Kahns algoritme tæller indgående pile: A og B har ingen, så A kommer først, derefter B. Når B's pile fjernes, bliver C og D frie og følger efter, og derefter E: rækkefølgen A, B, C, D, E. DFS-metoden besøger A, så C, så E; E bliver færdig først, så C, så A, og hver sættes forrest. Derefter besøger den B og D, som bliver færdige foran dem: rækkefølgen B, D, A, C, E. Begge rækkefølger er rigtige.
Kahn eller DFS?
Kahns algoritme, udgivet af Arthur Kahn i 1962, arbejder fremad: den ved altid, hvilke opgaver der kan startes nu, hvilket passer godt til planlægning, og den kan vælge mellem frie opgaver efter en hvilken som helst regel, for eksempel alfabetisk rækkefølge. DFS-metoden, gjort populær af Robert Tarjan i 1976, arbejder baglæns fra enderne og kræver kun en dybde-først-søgning. Begge bruger tid, der vokser med antallet af knuder plus kanter.
Anvendelser
Byggeværktøjer som make kompilerer filer efter de filer, de afhænger af. Pakkehåndteringer installerer biblioteker i afhængighedsrækkefølge. Regneark genberegner en celle efter de celler, dens formel bruger. Universiteter tjekker, at forudsætningerne for kurser kan opfyldes, compilere ordner instruktioner, og datapipelines kører hvert trin, når dets input er klar. Unix-kommandoen tsort laver selv en topologisk sortering.
Udforsk det
Åbn appen, og tryk på Trin. Pilene siger, hvilken knude der skal komme før hvilken. Med Kahns algoritme tæller tallet på hver knude dens resterende indgående pile, og frie knuder er blå. Med DFS-metoden er blå knuder under besøg, og grønne er placeret. Rækkefølgen vokser i rækken under grafen. Sæt kryds ved Tilføj en kreds, og se begge metoder opdage, at der ikke findes nogen rækkefølge.
Ofte stillede spørgsmål
Hvad betyder topologisk her?
Navnet kommer fra topologi, læren om, hvordan ting hænger sammen, frem for deres nøjagtige form. Rækkefølgen afhænger kun af, hvilke knuder der er forbundet med pile, ikke af, hvor de er tegnet.
Hvordan finder jeg kredsen, når der ikke er nogen rækkefølge?
DFS-metoden viser den direkte: kanten til en knude, der stadig er under besøg, sammen med stien af knuder under besøg, er kredsen. Kahns algoritme fortæller kun, hvilke knuder der sidder fast; en søgning blandt dem finder kredsen.
Kan jeg vælge en bestemt rækkefølge blandt de gyldige?
Ja. Når flere knuder er frie i Kahns algoritme, vælger du den, du foretrækker, for eksempel det mindste bogstav eller den mest presserende opgave. Med en prioritetskø får du den rækkefølge, der kommer først alfabetisk.
Hvordan bruges topologisk sortering til korteste veje?
I en orienteret acyklisk graf finder du alle korteste veje fra en start i ét gennemløb ved at opdatere afstandene langs hver knudes kanter i topologisk rækkefølge, selv med negative kanter, og hurtigere end Dijkstra eller Bellman–Ford.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv topologisk sortering