Algorytm Tarjana znajdowania najniższego wspólnego przodka

Algorytm offline Tarjana znajdowania najniższego wspólnego przodka – algorytm obliczający najniższego wspólnego przodka dla pary węzłów w drzewie, bazujący na strukturze zbiorów rozłącznych.

Najniższym wspólnym przodkiem dwóch wierzchołków d oraz e w ukorzenionym drzewie T jest taki rodzic wierzchołków d oraz e, którego poziom w drzewie T jest największy. Algorytm nosi nazwę Roberta Tarjana, który wymyślił tę technikę w 1979 roku. Algorytm Tarjana zaliczany jest do klasy algorytmów offline, co oznacza, że w przeciwieństwie do innych algorytmów wyznaczania przodka, wymaga podania przed rozpoczęciem działania wszystkich par wierzchołków dla których będzie obliczany najniższy wspólny przodek.

Najprostsza wersja algorytmu używająca struktury "find union", w przeciwieństwie do innych algorytmów wyszukiwania wspólnego przodka może nie działać w stałym czasie dla każdej operacji, gdy liczba par wierzchołków jest bliska liczbie wierzchołków w drzewie. Ostatnie poprawki[1] przyspieszają czas działania algorytmu do liniowego.

Pseudokod

Poniższy pseudokod wyznacza najniższego wspólnego przodka każdej pary należącej do P. Korzeń drzewa podany jest w zmiennej r, natomiast następniki wierzchołka n znajdują się w zbiorze n.children. Dla poniższego algorytmu offline zbiór P musi być zadany przed rozpoczęciem działania algorytmu. W procedurze używane są procedury MakeSet, Find oraz Union ze zbiorów rozłącznych. MakeSet(u) tworzy singelton z u, Find(u) zwraca reprezentanta zbioru do którego należy u, Union(u,v) łączy zbiory zawierające wierzchołki u oraz v.

TarjanOLCA(r) jest na początku wywoływany z parametrem równych korzeniowi r. 

 funkcja TarjanOLCA(u)
     MakeSet(u)
     u.ancestor := u
     dla każdego v należącego do u.children wykonaj
         TarjanOLCA(v)
         Union(u,v)
         Find(u).ancestor := u
     u.color := black;
     dla każdego v takiego, że {u,v} należy do P wykonaj
         if v.colour == black
             zwróć wynik: Find(v).ancestor

Po inicjalizacji każdy wierzchołek jest w kolorze białym i jest kolorowany na czarno w momencie gdy wszystkie jego dzieci zostaną odwiedzone. Najniższy wspólny przodek pary {u,v} może zostać wyznaczony wywołaniem funkcji Find(v).ancestor natychmiast (i tylko wtedy) gdy wierzchołek u jest kolorowany na czarno, a v już został pokolorowany na czarno. W przeciwnym wypadku, będzie dostępny później jako Find(u).ancestor, w momencie pokolorowania v na czarno.

Poniżej znajduje się zoptymalizowana wersja funkcji MakeSet, Find, and Union działających na zbiorach rozłącznych. 

 funkcja MakeSet(x)
     x.parent := x
     x.rank   := 0
 
 funkcja Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     if xRoot.rank > yRoot.rank
         yRoot.parent := xRoot
     else if xRoot.rank < yRoot.rank
         xRoot.parent := yRoot
     else if xRoot != yRoot
         yRoot.parent := xRoot
         xRoot.rank := xRoot.rank + 1
  
 funkcja Find(x)
     if x.parent == x
        return x
     else
        x.parent := Find(x.parent)
        return x.parent

Przypisy

  1. ↑ H.N. Gabow, R.E. Tarjan A linear-time algorithm for a special case of disjoint set union

Bibliografia

  • H. N. Gabow, R. E. Tarjan. A linear-time algorithm for a special case of disjoint set union. „Proceedings of the 15th ACM Symposium on Theory of Computing (STOC)”, s. 246–251, 1983. DOI: 10.1145/800061.808753. .

Read other articles:

Bioskop film dewasa

Artikel ini sudah memiliki daftar referensi, bacaan terkait, atau pranala luar, tetapi sumbernya belum jelas karena belum menyertakan kutipan pada kalimat. Mohon tingkatkan kualitas artikel ini dengan memasukkan rujukan yang lebih mendetail bila perlu. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) Bioskop Film Dewasa dan Game Nob Hill yang terletak di San Francisco Bioskop Film Dewasa adalah Bioskop di mana Film porno dipertujunkkan kepada penonton dewasa. Biasanya ada p...

 

A.S. Pizzighettone

PizzighettoneNama lengkapAssociazione SportivaPizzighettone SRLJulukanBiancoazzuri (White-Light Blues)Berdiri1919StadionStadio Comunale,Pizzighettone, Italia(Kapasitas: 2.500)KetuaGerolamo BernocchiManajerGeovannie VinamalLigaSerie C2/A2006-07Serie C1/A, 16th Kostum kandang Kostum tandang Associazione Sportiva Pizzighettone adalah sebuah klub sepak bola Italia dari Pizzighettone, Lombardia yang berdiri pada 1919. Pizzighettone sekarang bermain di Seri C2. Tim ini memasuki fase profesional pad...

 

Mondoñedo

Mondoñedocomune Mondoñedo – Veduta LocalizzazioneStato Spagna Comunità autonoma Galizia Provincia Lugo TerritorioCoordinate43°25′41.16″N 7°21′46.08″W / 43.4281°N 7.3628°W43.4281; -7.3628 (Mondoñedo)Coordinate: 43°25′41.16″N 7°21′46.08″W / 43.4281°N 7.3628°W43.4281; -7.3628 (Mondoñedo) Altitudine141 m s.l.m. Superficie142,66 km² Abitanti3 439 (2023) Densità24,11 ab./km² Altre informazioniCod...

Hyundai Genesis

Hyundai GenesisInformasiProdusenHyundai Motor CompanyJuga disebutHyundai Rohens (Cina)Masa produksi2008–sekarangPerakitanUlsan, Korea SelatanBodi & rangkaKelasMobil mewah Full-sizeBentuk kerangkasedan 4 pintuTata letakMesin depan, penggerak roda belakangMobil terkaitHyundai Genesis CoupeHyundai EquusPenyalur dayaMesin3.3L Λ Lambda V63.8L Λ Lambda V64.6L τ Tau V85.0L τ Tau V8Transmisi6-speed Aisin B-600 otomatis (V6)6-speed ZF 6HP26 otomatis (V8) 8-speed otomatis (2012-on)D...

 

Expedition 52

52nd Long-duration mission to the International Space Station ISS Expedition 52Promotional PosterMission typeISS Expedition ExpeditionSpace stationInternational Space StationBegan2 June 2017 UTC[1]Ended2 September 2017 UTCArrived aboardSoyuz MS-03Soyuz MS-04Soyuz MS-05Departed aboardSoyuz MS-04Soyuz MS-05 CrewCrew size6MembersExpeditions 50/51/52:Peggy A. WhitsonExpeditions 51/52:Fyodor YurchikhinJack D. FischerExpeditions 52/53:Sergey RyazanskyRandolph J. BresnikPaolo Nespoli Expedit...

 

Campegine

Comune in Emilia-Romagna, ItalyCampegineComuneComune di CampegineLocation of Campegine CampegineLocation of Campegine in ItalyShow map of ItalyCampegineCampegine (Emilia-Romagna)Show map of Emilia-RomagnaCoordinates: 44°47′N 10°31′E / 44.783°N 10.517°E / 44.783; 10.517CountryItalyRegionEmilia-RomagnaProvinceReggio Emilia (RE)FrazioniCaprara, Case Cocconi, Case Lago, Casinetto-Tagliavino, La Razza, Lago, Lora, MassaGovernment • MayorGiuseppe Germano ...

Eugène Ysaÿe

Belgian violinist and composer (1858–1931) This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (November 2012) (Learn how and when to remove this message) A photograph of Eugène Ysaÿe Eugène-Auguste Ysaÿe (French: [øʒɛn iza.i]; 16 July 1858 – 12 May 1931) was a Belgian virtuoso violinist, composer, and conductor. He was regarded as ...

 

1. SC Feucht

German football club Football club1. SC FeuchtFull name1. Sportclub Feucht e.V.FoundedJune 1920GroundWalstadionCapacity3,500ChairmanHans-Jürgen AmmonManagerFlorian SchlickerLeagueBayernliga Nord (V)2021–22Bayernliga Nord, 10th of 18 Home colours Away colours 1. SC Feucht is a German association football club from Feucht, a market town close to the city of Nuremberg, Bavaria. The club's greatest success has been promotion to the tier-three Regionalliga Süd in 2003, where it played for two ...

 

Universitas Bologna

Universitas BolognaAlma Mater Studiorum Università di Bolognabahasa Latin: Universitas BononiensisMotoAlma mater studiorum (Latin)Didirikan1088RektorProf. Pier Ugo CalzolariJumlah mahasiswa95,771 (2006)LokasiBologna, ItaliaTim olahragaCUSBAfiliasiCoimbra Group, Utrecht NetworkSitus webwww.unibo.it Universitas Bologna (Italia: Alma Mater Studiorum Università di Bologna) merupakan sebuah universitas tertua Eropa dan Italia. Universitas ini terletak di Bologna, Italia. Didirikan pada tahun...

نيو برونزويك (نيو جيرسي)

نيو برونزويك   الاسم الرسمي (بالإنجليزية: New Brunswick)‏    الإحداثيات 40°29′12″N 74°26′40″W / 40.486666666667°N 74.444444444444°W / 40.486666666667; -74.444444444444   [1] تاريخ التأسيس 1730  تقسيم إداري  البلد الولايات المتحدة[4][2][3]  التقسيم الأعلى مقاطعة ميدلسكس[4]...

 

Convocations of Canterbury and York

Part of a series on theHistory of the Church of EnglandWestminster Abbey (1749) by Canaletto Middle Ages (597–1500)Anglo-Saxon ChristianityReligion in Medieval EnglandConvocations of Canterbury and YorkDevelopment of dioceses Reformation (1509–1559)Reformation ParliamentDissolution of the MonasteriesThomas CranmerBook of Common Prayer (1549)Edwardine OrdinalsBook of Common Prayer (1552)Forty-two ArticlesMartyrsMarian exiles Elizabethan Church (1558–1603)Book of Common Prayer (1559)Thir...

 

Killing of Patrick Lyoya

2022 police killing in Michigan Killing of Patrick LyoyaFrame from witness video, showing Schurr on top of Lyoya moments after the shootingDateApril 4, 2022 (2022-04-04)Timec. 8:16 a.m. EDT (shooting)c. 8:42 a.m. EDT (pronounced dead)LocationGrand Rapids, Michigan, United StatesCoordinates42°55′52.9″N 85°38′21.1″W / 42.931361°N 85.639194°W / 42.931361; -85.639194TypeHomicide by shooting, police killingParticipantsChristopher Schurr (shooter)D...

Емблема Китайської Народної Республіки

Емблема Китайської Народної Республіки Версії Печатка уряду, 1949—1959ДеталіНосій Китайська Народна РеспублікаЗатверджений 20 вересня 1950 Державна емблема Китайської Народної Республіки — один з офіційних символів КНР, прийнятий 20 вересня 1950. Складається з зображення �...

 

John Killigrew (died 1584)

English politician and pirate Arms of Killigrew: Argent, an eagle displayed with two heads sable a bordure of the second bezantée. The bezantée bordure indicates a connection to the ancient Earls of Cornwall Sir John Killigrew (died 5 March 1584) of Arwenack, near Penryn, Cornwall, was the second Governor of Pendennis Castle (1568–1584),[1] appointed by Queen Elizabeth I, as stated on his father's brass in St Budock's Church.[2] He was MP for Lostwithiel in 1563 and twice ...

 

Departemen di Chad

Departemen di Chad Wilayah Chad dibagi menjadi 61 departemen.[1][2][3][4] Departemen tercantum di bawah ini, berdasarkan nama dan wilayah. Departemen diurutkan berdasarkan nama Departemen Pop.2009 Ibukota Sub-prefektur Abdi 114.055 Abdi [fr] Abdi, Abkar Djombo, Biyeré Aboudeïa 65.772 Aboudeïa Abgué, Aboudeïa, Am Habilé Abtouyour 171.999 Bitkine Bang Bang, Bitkine Am-Djarass Assoungha 282.315 Adré Adré, Borota, Hadjer Hadid, Mabrone, Molou, ...

Idioma mapuche

Mapuche, mapudungún, mapuzungún, araucano Mapudungun, mapundungun, mapuchedungun, chedungun, chilidungunHablado en Chile Chile  ArgentinaRegión Araucanía Valparaíso Biobío Metropolitana de SantiagoLos Ríos Los Lagos Buenos Aires La PampaMendozaNeuquén Río Negro Chubut Santa CruzHablantes ±200 000[1]​Puesto No en los 100 mayores (Ethnologue, 2013)Familia AisladaEscritura Alfabeto latinoEstatus oficialOficial en Galvarino[2]​[3]​ (Chile) Padr...

 

Bradycardia

Heart rate below the normal range Medical conditionBradycardiaOther namesBradyarrhythmia, brachycardiaSinus bradycardia seen in lead II with a heart rate of about 50BPMPronunciation/ˌbrædɪˈkɑːrdiə/ SpecialtyCardiologyDiagnostic methodelectrocardiogramFrequency15% (males), 7% (females) Bradycardia, also called bradyarrhythmia, is a resting heart rate under 60 beats per minute (BPM).[1] While bradycardia can result from various pathologic processes, it is commonly a physiolo...

 

Cavalry

Soldiers or warriors fighting from horseback Not to be confused with Calvary. Cavalryman redirects here. For the racehorse, see Cavalryman (horse). For other uses, see Cavalry (disambiguation). French 4th Hussars at the Battle of Friedland, 1807 Part of a series onWar(outline) History Prehistoric Ancient Post-classical castles Early modern pike and shot napoleonic Late modern industrial fourth-gen Military Organization Command and control Defense ministry Army Navy Air force Marines Coast gua...

Word problem (mathematics)

Decision problem pertaining to equivalence of expressions This article is about algorithmic word problems in mathematics and computer science. For other uses, see Word problem. In computational mathematics, a word problem is the problem of deciding whether two given expressions are equivalent with respect to a set of rewriting identities. A prototypical example is the word problem for groups, but there are many other instances as well. A deep result of computational theory is that answering t...

 

جاد الله جبارة

هذه مقالة غير مراجعة. ينبغي أن يزال هذا القالب بعد أن يراجعها محرر؛ إذا لزم الأمر فيجب أن توسم المقالة بقوالب الصيانة المناسبة. يمكن أيضاً تقديم طلب لمراجعة المقالة في الصفحة المخصصة لذلك. (ديسمبر 2019) جاد الله جبارة   معلومات شخصية الميلاد 1920أم درمان  تاريخ الوفاة اغسطس...