Дисјунктни-сет (структура података) — разлика између измена
Садржај обрисан Садржај додат
м Renamed template |
clean up |
||
Ред 1:
{{Neprovereni seminarski}}
{{
[[Датотека:Dsu disjoint sets init.svg|thumb|360px|''MakeSet'' creates 8 singletons.]]
[[Датотека:Dsu disjoint sets final.svg|thumb|360px|After some operations of ''Union'', some sets are grouped together.]]
Ред 26:
Представник сваког сета је корен стабла тог скупа је. Операција Нађи следи родитељске чворове док не стигне до корена.
Унија комбинује два стабла у једно прикључивањем корена једног корену другог стабла. Један од начина имплементације може бити следећи:
'''function''' ''MakeSet''(x)
Линија 73 ⟶ 72:
'''<big>Примена</big>'''
Примена дисјунктивног-сета структура података модела подела скупа [[Partition of a set|partitioning of a set]], је на пример да пратите повезане компоненте ([[Connected component (graph theory)|connected components]]) неусмереног графа ([[undirected graph]]). Овај модел се затим може користити за одређивање да ли две гране припадају истом чвору, или да ли ће додавање границе између њих резултовати у циклусом. Унија-Нађи алгоритам се користи у имплементацијама високих перформанси [[Unification (computer science)|Unification]].
== Историја ==
Док су идеје које су се користиле у дисјунктивним-сет шумама дуго били познате, [[Роберт Тарџан|Robert Tarjan]] је био први који је доказао горње границе (и ограничена верзију доње границе) у смислу инверзности [[Ackermann function]], 1975.
До тода, најбоља граница за време по операцији, доказано од стране [[Џон Хопкрофт|Hopcroft]] и [[Jeffrey Ullman|Ullman]],<ref>{{cite journal |last1=Hopcroft|first1=J. E. |author1-link=John Hopcroft |last2=Ullman|first2=J. D. |author2-link=Jeffrey Ullman |year=1973|title=Set Merging Algorithms |journal=SIAM Journal on Computing |volume=2 |issue=4 |doi=10.1137/0202024|pages=294-303}}</ref>
био је доказ [[Proof of O(log*n) time complexity of union–find|O(log<sup>*</sup> n)]] , итеративни алгоритам од n, још једна споро растућа функција(али не спора колико и инверзна Ackermann function).
| |||