Topološko uređenje — разлика између измена
Садржај обрисан Садржај додат
м Бот: уклоњен шаблон: Link FA |
м Бот: исправљена преусмерења |
||
Ред 15:
== Алгоритми ==
Уобичајени алгоритми за тополошко сортирање имају линеарну сложеност по броју чворова плус броју грана -{([[
Један од ових алгоритама ради на следећи начин. Прво се сачини списак чворова у које ниједна грана не улази (најмање један такав чвор (са [[Степен (теорија графова)|улазним степеном]] нула) мора да постоји ако је граф ацикличан), и оне се сместе у [[ред (структура података)|ред]] -{Q}-. Затим,
Ред 31:
Ако овај алгоритам заврши пре него што испише све чворове графа, то значи да граф има најмање један цикл, и да није усмерени ациклични граф, па је тополошко сортирање немогуће. Због чињенице да сортирање није јединствено, структура -{Q}- не мора да буде ред; може се користити и [[стек (
== Спољашње везе ==
| |||