Topologisk sortering er arbeidet med å sortere nodene i en graf slik at naboer listes i rett innebyrdes orden. Det forutsettes at to noder bare har en rettet kant seg imellom, og at grafen er asyklisk.
Problemstillingen opptrer for eksempel i prosjektplanlegging, og beregninger i regneark, der avhengigheter gjør at arbeid må utføres i rett rekkefølge. Grafens noder er da henholdsvis aktivitet i prosjektet eller en celleberegning. right Den avbildede rettede asykliske graf (t.h.) har flere mulige topologiske sorteringer: 7,5,3,11,8,2,9,10 7,5,11,2,3,10,8,9 3,7,8,5,11,10,9,2 En vanlig algoritme for å finne en av løsningene, er da å Initielt finne ut hvilke noder som er naboer (a har nabo b kun hvis det fins en rettet kant fra a til b) regn ut inn-graden g(n) til hver node n i grafen. Noder med g(n) lik 0 legges i mengden STARTPUNKT I en løkke vil man, sålenge det finnes noder i STARTPUNKT velge ut en node i fra mengden STARTPUNKT skriv ut i fjern i fra STARTPUNKT for hver av i's naboer, j reduser g(j) med 1 hvis g(j) har blitt 0, legg j til mengden STARTPUNKT Utskriften inneholder den sorterte liste. Hvis grafen er syklisk avsløres det med at g(j) har antatt negative verdier.
Kategori:Sorteringsalgoritmer