รหัสเทียม ด้านล่างอธิบายถึง ปมบรรพบุรุษร่วมใกล้สุดของแต่ละคู่ปมในต้นไม้ P โดยมี r เป็นปมราก ซึ่งลูกของปม n จะอยู่ในเซตn.children ทั้งนี้เนื่องจากขั้นตอนวิธีการนี้เป็นแบบออฟไลน์ ดังนั้น เซตของ P จะต้องถูกกำหนดเป็นพิเศษล่วงหน้า ขั้นตอนวิธีนี้ใช้การดำเนินการกับป่าไม้ของกลุ่มเซตไม่มีตัวร่วม (disjoint-set forest) 3 แบบ คือ
MakeSet(u) : สร้างเซตใหม่ที่มี u เป็นสมาชิกเพียงตัวเดียว
Find(u) : หาหมายเลขเซตที่ u เป็นสมาชิกอยู่
Union(u,v) : ยูเนียนเซต u กับ เซต v
โดยมี TarjanOLCA(r) เป็นการเรียกฟังก์ชันโดยเริ่มที่ปมราก r
function TarjanOLCA(u) MakeSet(u); u.ancestor := u; for each v in u.children do TarjanOLCA(v); Union(u,v); Find(u).ancestor := u; u.colour := black; for each v such that {u,v} in P do if v.colour == black print "Tarjan's Least Common Ancestor of " + u + " and " + v + " is " + Find(v).ancestor + ".";
ขณะเริ่มต้นแต่ละปมจะถูกกำหนดให้มีสีขาว และจะถูกกำหนดเป็นสีดำก็ต่อเมื่อปมนั้นและลูกทั้งหมดของปมนั้นถูกผ่านแล้ว ปมบรรพบุรุษร่วมใกล้สุดของคู่ปม {u,v} จะสามารถหาได้จาก Find(v).ancestor ในทันทีได้ก็ต่อเมื่อ หลังจากที่ปม u ถูกเปลี่ยนเป็นสีดำเรียบร้อยแล้ว โดยมีเงื่อนไขว่า ปม v จะต้องเป็นสีดำแล้ว ไม่เช่นนั้นจะสามารถหาได้จาก Find(u).ancestor ในทันทีหลังจากที่ ปม v ถูกเปลี่ยนเป็นสีดำ
รหัสเทียมด้านล่างต่อไปนี้ เป็นรหัสเทียมอ้างอิงถึงการดำเนินการทั้ง 3 แบบที่ได้รับการปรับปรุงให้เหมาะสมสำหรับป่าไม้ของกลุ่มเซตไม่มีตัวร่วม อันได้แก่ MakeSet, Find และ Union
function MakeSet(x) x.parent := x x.rank := 0
function 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
function Find(x) if x.parent == x return x else x.parent := Find(x.parent) return x.parent
อ้างอิง
Gabow, H. N.; Tarjan, R. E. (1983), "A linear-time algorithm for a special case of disjoint set union", Proceedings of the 15th ACM Symposium on Theory of Computing (STOC), pp. 246–251, doi:10.1145/800061.808753
Tarjan, R. E. (1979), "Applications of path compression on balanced trees", Journal of the ACM 26 (4): 690–715, doi:10.1145/322154.32216
สิงหาคม 16, 2021
นตอนว, การหาปมบรรพบ, ษร, วมใกล, ดของค, ปมของทาร, จาน, บทความน, อาจต, องการตรวจสอบต, นฉบ, ในด, านไวยากรณ, ปแบบการเข, ยน, การเร, ยบเร, ยง, ณภาพ, หร, อการสะกด, ณสามารถช, วยพ, ฒนาบทความได, ระว, งส, บสนก, tarjan, strongly, connected, components, algorithm, ในว, ทยา. bthkhwamnixactxngkartrwcsxbtnchbb indaniwyakrn rupaebbkarekhiyn kareriyberiyng khunphaph hruxkarsakd khunsamarthchwyphthnabthkhwamidrawngsbsnkb Tarjan s strongly connected components algorithm inwithyakarkhxmphiwetxr khntxnwithikarhapmbrrphburusrwmiklsudkhxngkhupmkhxngtharcan xngkvs Tarjan s off line least common ancestors algorithm xnthicringaelw least khwrcaepn lowest khuxkhntxnwithiinkarkhanwnhabrrphburusrwmtasud lowest common ancestors sahrbthuk khukhxngpmintnim rooted tree odymiphunthaninkarkhanwnhacakokhrngsrangkhxmulthieriykwaokhrngsrangkhxmulestimmiswnrwm khntxnwithiniidthuktngchuxtam Robert Tarjan phusungkhnphbklwithiniinpi 1979pmbrrphburusrwmiklsudkhxngrahwangkhupm d aela e intnim T khux pm g sungepnpmbrrphburuskhxngthngpm d aelapm e thiiklcakpmrakmakthisudkhntxnwithikhxngtharcan imehmuxnkbkhntxnwithikarhapmbrrphburusrwmiklsudkhxngkhupmxun enuxngcakepnkhntxnwithixxfiln sungkhuxkhntxnwithithicatxngpxnkhxmulnaekhathnghmdkxnerimkaraekpyhatamkhntxnwithi nxkcaknikhntxnwithikhxngtharcan yngepnkhntxnwithithiichokhrngsrangkhxmulthieriykwa karyueniynaelakarkhnha thaihrayaewlathiichsahrbkhntxnwithiniimepnkhakhngtw inkrnithimicanwnkhukhxngpmethakbcanwnkhxngpmthnghmd thaihaetktangcakkhntxnwithixun thiimidichokhrngsrangkhxmulkaryueniynaelakarkhnha txmainpi 1983 Gabow aela Tarjan idthakarprbprungprasiththiphaphkhxngkhntxnwithiihichrayaewlaerwkhunepnaebbechingesn O n rhsethiym aekikhrhsethiym danlangxthibaythung pmbrrphburusrwmiklsudkhxngaetlakhupmintnim P odymi r epnpmrak sunglukkhxngpm n caxyuinest n children thngnienuxngcakkhntxnwithikarniepnaebbxxfiln dngnn estkhxng P catxngthukkahndepnphiesslwnghna khntxnwithiniichkardaeninkarkbpaimkhxngklumestimmitwrwm disjoint set forest 3 aebb khux MakeSet u srangestihmthimi u epnsmachikephiyngtwediyw Find u hahmayelkhestthi u epnsmachikxyu Union u v yueniynest u kb est v odymi TarjanOLCA r epnkareriykfngkchnodyerimthipmrak rfunction TarjanOLCA u MakeSet u u ancestor u for each v in u children do TarjanOLCA v Union u v Find u ancestor u u colour black for each v such that u v in P do if v colour black print Tarjan s Least Common Ancestor of u and v is Find v ancestor khnaerimtnaetlapmcathukkahndihmisikhaw aelacathukkahndepnsidaktxemuxpmnnaelalukthnghmdkhxngpmnnthukphanaelw pmbrrphburusrwmiklsudkhxngkhupm u v casamarthhaidcak Find v ancestor inthnthiidktxemux hlngcakthipm u thukepliynepnsidaeriybrxyaelw odymienguxnikhwa pm v catxngepnsidaaelw imechnnncasamarthhaidcak Find u ancestor inthnthihlngcakthi pm v thukepliynepnsidarhsethiymdanlangtxipni epnrhsethiymxangxingthungkardaeninkarthng 3 aebbthiidrbkarprbprungihehmaasmsahrbpaimkhxngklumestimmitwrwm xnidaek MakeSet Find aela Union function MakeSet x x parent x x rank 0 function Union x y xRoot Find x yRoot Find y if xRoot rank gt yRoot rank yRoot parent xRoot else if xRoot rank lt yRoot rank xRoot parent yRoot else if xRoot yRoot yRoot parent xRoot xRoot rank xRoot rank 1 function Find x if x parent x return x else x parent Find x parent return x parentxangxing aekikhGabow H N Tarjan R E 1983 A linear time algorithm for a special case of disjoint set union Proceedings of the 15th ACM Symposium on Theory of Computing STOC pp 246 251 doi 10 1145 800061 808753 Tarjan R E 1979 Applications of path compression on balanced trees Journal of the ACM 26 4 690 715 doi 10 1145 322154 32216ekhathungcak https th wikipedia org w index php title khntxnwithikarhapmbrrphburusrwmiklsudkhxngkhupmkhxngtharcan amp oldid 4703388, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
