Placerade
Väntar på att placeras
Kontrollerade kanter

  • Aktuell
  • Fria eller besöks
  • Placerade
  • Cykel

Mer om topologisk sortering

Topologisk sortering

Strumpor före skor, grund före väggar, en kurs före kursen som kräver den. En topologisk sortering ställer noderna i en graf med enkelriktade kanter på en rad där varje kant pekar framåt. Välj Kahns algoritm eller DFS-metoden, gå steg för steg och se ordningen växa, och lägg till en cykel för att se varför ingen ordning då är möjlig. Tryck på Spela för att se ordningen växa, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst. Varje kant är enkelriktad, som pilen visar: tänk på den som "det här kommer före det där". Välj metod: Kahns algoritm placerar först noder utan ingående kanter, och talet på varje nod är hur många ingående kanter den har kvar; DFS-metoden sätter varje nod längst fram när allt efter den är placerat. Raden under grafen är ordningen hittills. Kryssa i Lägg till en cykel för att se hur varje metod hittar en. Ny graf skapar en annan graf; välj hur många noder och kanter den har. När brädet är markerat stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.

Hur det fungerar

  1. Välj Kahns algoritm eller DFS-metoden.
  2. Tryck på Spela, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst.
  3. Se ordningen växa under grafen. Kryssa i Lägg till en cykel för att se hur varje metod hittar en.

Kahns algoritm

Räkna för varje nod hur många kanter som pekar på den. En nod utan några beror inte på något, så den kan komma först. Placera en sådan nod och ta bort dess utgående kanter: noderna de pekade på har nu en ingående kant mindre, och några kan nå noll och bli fria. Fortsätt placera fria noder tills inga finns kvar. Om några noder aldrig blev fria väntar de på varandra i en cykel, och det finns ingen topologisk ordning.

DFS-metoden

Kör en djupet-först-sökning från varje obesökt nod. En nod är färdig när allt som kan nås från den är färdigt, så allt som måste komma efter den är redan placerat. Sätt varje färdig nod längst fram i ordningen, så blir ordningen rätt. Om sökningen följer en kant till en nod som den fortfarande är inne i, sluter den kanten en cykel, och då finns det inte heller någon ordning.

Ofta ställda frågor

Vad är en topologisk sortering?

En ordning av noderna i en riktad graf där varje kant går från en tidigare nod till en senare. Om kanterna betyder "måste komma före" är det en ordning där alla uppgifter kan utföras.

När finns en topologisk ordning?

Precis när grafen saknar riktad cykel: den är en riktad acyklisk graf, eller DAG. Med en cykel skulle varje nod på den behöva komma före sig själv.

Är den topologiska ordningen unik?

Oftast inte. När två noder inte förbinds av en kedja av kanter kan vilken som helst av dem komma först, så en graf kan ha många giltiga ordningar. Kahns algoritm och DFS-metoden ger ofta olika.

Hur snabb är en topologisk sortering?

Båda metoderna tittar på varje nod och varje kant ett fast antal gånger, så arbetet växer med antalet noder plus antalet kanter.

Skickas min graf någonstans?

Nej. Grafen skapas och sorteras i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Gå till Editor