- Huidig
- Vrij of wordt bezocht
- Geplaatst
- Cyclus
Topologisch sorteren
Sokken voor schoenen, fundering voor muren, een vak voor het vak dat erop voortbouwt. Topologisch sorteren zet de knopen van een graaf met eenrichtingskanten op een rij waarin elke kant vooruit wijst. Kies het algoritme van Kahn of de DFS-methode en ga stap voor stap om de volgorde te zien groeien, en voeg een cyclus toe om te zien waarom er dan geen volgorde mogelijk is. Druk op Afspelen om de volgorde te zien groeien, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen. Elke kant is eenrichtingsverkeer, zoals de pijl laat zien: lees hem als "dit komt voor dat". Kies de methode: het algoritme van Kahn plaatst eerst knopen zonder inkomende kanten, en het getal op elke knoop is hoeveel inkomende kanten die nog heeft; de DFS-methode zet elke knoop vooraan zodra alles erna geplaatst is. De rij onder de graaf is de volgorde tot nu toe. Vink Cyclus toevoegen aan om te zien hoe elke methode er een vindt. Nieuwe graaf maakt een andere graaf; kies hoeveel knopen en kanten die heeft. Als het bord geselecteerd is, gaan de pijltjestoetsen een stap verder of terug, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het einde.
Hoe het werkt
- Kies het algoritme van Kahn of de DFS-methode.
- Druk op Afspelen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen.
- Volg hoe de volgorde onder de graaf groeit. Vink Cyclus toevoegen aan om te zien hoe elke methode er een vindt.
Het algoritme van Kahn
Tel voor elke knoop hoeveel kanten ernaartoe wijzen. Een knoop zonder hangt van niets af, dus die kan eerst. Plaats zo'n knoop en haal zijn uitgaande kanten weg: de knopen waar ze naartoe wezen, hebben nu één inkomende kant minder, en sommige komen op nul en worden vrij. Plaats vrije knopen tot er geen meer over is. Als sommige knopen nooit vrij werden, wachten ze in een cyclus op elkaar, en bestaat er geen topologische volgorde.
De DFS-methode
Start diepte-eerst zoeken vanaf elke nog niet bezochte knoop. Een knoop is afgerond als alles wat ervandaan bereikbaar is, afgerond is, dus alles wat erna moet komen, is al geplaatst. Zet elke afgeronde knoop vooraan in de volgorde, en de volgorde klopt vanzelf. Als het zoeken een kant volgt naar een knoop waar het nog in zit, sluit die kant een cyclus, en ook dan bestaat er geen volgorde.
Veelgestelde vragen
Wat is topologisch sorteren?
Een volgorde van de knopen van een gerichte graaf waarin elke kant van een eerdere naar een latere knoop gaat. Als de kanten "moet eerder komen dan" betekenen, is het een volgorde waarin alle taken gedaan kunnen worden.
Wanneer bestaat er een topologische volgorde?
Precies als de graaf geen gerichte cyclus heeft: dan is het een gerichte acyclische graaf, of DAG. Met een cyclus zou elke knoop erop voor zichzelf moeten komen.
Is de topologische volgorde uniek?
Meestal niet. Als twee knopen niet via een keten van kanten verbonden zijn, kan elk van beide eerst, dus een graaf kan veel geldige volgordes hebben. Het algoritme van Kahn en de DFS-methode geven er vaak verschillende.
Hoe snel is topologisch sorteren?
Beide methoden bekijken elke knoop en elke kant een vast aantal keer, dus het werk groeit met het aantal knopen plus het aantal kanten.
Wordt mijn graaf ergens heen gestuurd?
Nee. De graaf wordt in je browser gemaakt en gesorteerd, en je laatste instellingen blijven in de lokale opslag van deze browser.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Ga naar Editor