Topologisch sorteren met het algoritme van Kahn
Taken ordenen die van andere taken afhangen
Topologisch sorteren met het algoritme van Kahn is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 1 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat een topologische volgorde is
Een topologische volgorde bevat elke knoop van een gerichte graaf, zodat elke verbinding van eerder naar later wijst. Denk aan taken vóór de taken die ervan afhankelijk zijn.
Alleen DAG's toegestaan
Dit werkt alleen op een DAG, een gerichte acyclische graaf. Als er een cyclus bestaat, kan geen geldige volgorde aan elke afhankelijkheid voldoen.
Het idee van de in-graad
Het algoritme van Kahn steunt op de in-graad: het aantal verbindingen dat naar een knoop wijst. Een knoop met in-graad nul heeft geen onvervulde afhankelijkheden.
Elke in-graad tellen
Eerste doorgang: doorloop alle verbindingen en tel hoe vaak elke knoop een bestemming is. Zo krijg je de in-graad van elke knoop.
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1De wachtrij voor gereedstaande knopen vullen
Elke knoop met in-graad nul is meteen klaar, dus voeg je ze allemaal toe aan een wachtrij om te beginnen.
from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)Eén knoop verwerken
Haal een gereedstaande knoop uit de wachtrij en voeg die toe aan je volgorde. Dat is nu veilig, omdat niets wat nog over is ervan afhankelijk is.
u = q.popleft()
order.append(u)De buren vrijgeven
Verlaag voor elke buur de in-graad met één. Zodra een buur nul bereikt, is die klaar en komt die in de wachtrij.
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)Herhalen tot de wachtrij leeg is
Blijf knopen uit de wachtrij halen en buren vrijgeven tot de wachtrij leeg is. De volgorde groeit met één veilige knoop tegelijk totdat elke knoop is geplaatst.
Gratis een cyclus detecteren
Als je uiteindelijke volgorde minder dan n knopen bevat, heeft een cyclus de rest opgesloten. Met het algoritme van Kahn krijg je cyclusdetectie zonder extra kosten.
if len(order) < n:
print('cycle exists')De uitvoeringstijd
Elke knoop en verbinding wordt één keer bezocht, dus draait het algoritme van Kahn in O(V + E). Dat schaalt naar grafen met miljoenen verbindingen.
Veel geldige volgordes
Wanneer meerdere knopen tegelijk klaar zijn, kan elke knoop als volgende worden gekozen. Daarom heeft een DAG vaak veel geldige topologische volgordes, niet slechts één.
Snelle controle
Je voltooit het algoritme van Kahn, maar de volgorde bevat minder dan n knopen. Wat betekent dat?
Herhaling: algoritme van Kahn
Tel de in-graden, zet de nullen in de wachtrij, haal een knoop eruit, verlaag de in-graden van de buren en herhaal. Dat is een nette topologische sortering in O(V+E). 🚀
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Topologisch sorteren met het algoritme van Kahn” gratis?
Ja — de volledige tekst van “Topologisch sorteren met het algoritme van Kahn” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Topologisch sorteren met het algoritme van Kahn”?
Taken ordenen die van andere taken afhangen Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 1 van 4.
Hoe lang duurt de les “Topologisch sorteren met het algoritme van Kahn”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Topologisch sorteren met het algoritme van Kahn
- Cycli in gerichte grafen detecteren
- Sterk samenhangende componenten
- Bruggen en articulatiepunten