Topološko uređenje — разлика између измена
Садржај обрисан Садржај додат
м ispravke |
м Бот: уклоњен шаблон: Link FA |
||
Ред 1:
{{Spajanje|
У [[теорија графова|теорији графова]], '''тополошко сортирање''' [[усмерени ациклични граф|усмереног ацикличног графа]] је линеарно уређење његових чворова, које је компатибилно са парцијалним уређењем -{R}- [[индукована топологија|индукованим]] на чворовима где ''-{x}-'' долази пре ''-{y}-'' (-{xRy}-) ако постоји усмерен пут од ''-{x}-'' у ''-{y}-'' усмереном ацикличном графу. Еквивалентна дефиниција је да сваки чвор долази пре свих чворова до којих из њега постоји пут. Сваки усмерени ациклични граф има једно или више тополошких сортирања.
== Примери ==
Канонска примена тополошког сортирања је у прављењу распореда неких послова. Послови су представљени чворовима, и постоји грана од ''-{x}-'' до ''-{y}-'' ако посао ''-{x}-'' мора бити завршен пре него што се може прећи на посао ''-{y}-'' (на пример, машина за прање веша мора да заврши са прањем да би се веш простро на сушење). Тада тополошко сортирање даје редослед по којима се послови могу извршавати. Ово има разне примене у рачунарству. Осим тога, тополошко сортирање се може користити за једноставно проналажење најкраћих путева до свих чворова од неког чвора усмереног ацикличног графа.
{|
|[[Датотека:Directed acyclic graph.png|180п|лево]]
| Овај граф има многа исправна тополошка сортирања, међу којима су:
* 7,5,3,11,8,2,10,9
* 7,5,11,2,3,10,8,9
* 3,7,8,5,11,10,9,2
|}
==
Уобичајени алгоритми за тополошко сортирање имају линеарну сложеност по броју чворова плус броју грана -{([[Нотација великог О|Θ]](|V|+|E|))}-.
Један од ових алгоритама ради на следећи начин. Прво се сачини списак чворова у које ниједна грана не улази (најмање један такав чвор (са [[Степен (теорија графова)|улазним степеном]] нула) мора да постоји ако је граф ацикличан), и оне се сместе у [[ред (структура података)|ред]] -{Q}-. Затим,
-{Q}- ← скуп свих чворова без улазних грана
'''док''' -{Q}- није празно '''уради'''
уклони чвор -{n}- из -{Q}-
испиши -{n}-
'''за сваки''' чвор -{m}- са граном ''-{e}-'' из -{n}- у -{m}- '''уради'''
уклони грану -{e}- из графа
'''ако''' -{m}- нема других улазних грана '''онда'''
убаци -{m}- у -{Q}-
'''ако''' граф има грана '''онда'''
испиши поруку о грешци (граф има цикл)
Ако овај алгоритам заврши пре него што испише све чворове графа, то значи да граф има најмање један цикл, и да није усмерени ациклични граф, па је тополошко сортирање немогуће. Због чињенице да сортирање није јединствено, структура -{Q}- не мора да буде ред; може се користити и [[стек (структура података)|стек]], или просто скуп.
== Спољашње везе ==
* [http://www.nist.gov/dads/HTML/topologcsort.html ''-{NIST}-'' Речник алгоритама и структура података: тополошко сортирање]
* [http://everything2.com/?node_id=556079 тополошко сортирање на сајту ''-{everything2}-'']
== Литература ==
* -{Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ''Introduction to Algorithms''. MIT Press and McGraw-Hill.}-
** -{First Edition, 1990. ISBN 0-07-013143-0. Section 23.4: Topological sort, pp.485-488.}-
** -{Second Edition, 2001. ISBN 0-262-03293-7. 2001. Section 22.4: Topological sort, pp.549-552.}-
[[Категорија:Графовски алгоритми]]
[[Категорија:Алгоритми сортирања]]
|