- Aktuel
- Fri eller under besøg
- Placeret
- Kreds
Topologisk sortering
Strømper før sko, fundament før mure, et kursus før det kursus, der bygger på det. En topologisk sortering stiller knuderne i en graf med ensrettede kanter op på en række, hvor hver kant peger fremad. Vælg Kahns algoritme eller DFS-metoden, gå trin for trin igennem, og se rækkefølgen vokse, og tilføj en kreds for at se, hvorfor ingen rækkefølge så er mulig. Tryk på Afspil for at se rækkefølgen vokse, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst. Hver kant er ensrettet, som pilen viser: tænk på den som "det her kommer før det der". Vælg metoden: Kahns algoritme placerer først knuder uden indgående kanter, og tallet på hver knude er, hvor mange indgående kanter den stadig har; DFS-metoden sætter hver knude forrest, når alt efter den er placeret. Rækken under grafen er rækkefølgen indtil nu. Sæt kryds ved Tilføj en kreds for at se, hvordan hver metode finder en. Ny graf laver en anden graf; vælg, hvor mange knuder og kanter den har. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End springer til starten og slutningen.
Sådan virker det
- Vælg Kahns algoritme eller DFS-metoden.
- Tryk på Afspil, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst.
- Se rækkefølgen vokse under grafen. Sæt kryds ved Tilføj en kreds for at se, hvordan hver metode finder en.
Kahns algoritme
Tæl for hver knude, hvor mange kanter der peger på den. En knude uden nogen afhænger ikke af noget, så den kan komme først. Placér sådan en knude, og fjern dens udgående kanter: de knuder, de pegede på, har nu én indgående kant mindre, og nogle når måske nul og bliver frie. Bliv ved med at placere frie knuder, til der ikke er flere. Blev nogle knuder aldrig frie, venter de på hinanden i en kreds, og der findes ingen topologisk rækkefølge.
DFS-metoden
Kør en dybde-først-søgning fra hver knude, der ikke er besøgt. En knude er færdig, når alt, hvad der kan nås fra den, er færdigt, så alt, hvad der skal komme efter den, er allerede placeret. Sæt hver færdig knude forrest i rækkefølgen, så bliver rækkefølgen rigtig. Følger søgningen en kant til en knude, den stadig er inde i, lukker den kant en kreds, og igen findes der ingen rækkefølge.
Ofte stillede spørgsmål
Hvad er en topologisk sortering?
En rækkefølge af knuderne i en orienteret graf, hvor hver kant går fra en tidligere knude til en senere. Betyder kanterne "skal komme før", er det en rækkefølge, som alle opgaverne kan udføres i.
Hvornår findes en topologisk rækkefølge?
Netop når grafen ikke har nogen orienteret kreds: den er en orienteret acyklisk graf, eller DAG. Med en kreds skulle hver knude på den komme før sig selv.
Er den topologiske rækkefølge entydig?
Som regel ikke. Når to knuder ikke er forbundet af en kæde af kanter, kan hvilken som helst af dem komme først, så en graf kan have mange gyldige rækkefølger. Kahns algoritme og DFS-metoden giver ofte forskellige.
Hvor hurtig er en topologisk sortering?
Begge metoder ser på hver knude og hver kant et fast antal gange, så arbejdet vokser med antallet af knuder plus antallet af kanter.
Bliver min graf sendt nogen steder hen?
Nej. Grafen laves og sorteres i din browser, og dine seneste indstillinger gemmes i denne browsers lokale lager.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor