ขั้นตอนวิธีการหาปมบรรพบุรุษร่วมใกล้สุดของคู่ปมของทาร์จาน

ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีการหาปมบรรพบุรุษร่วมใกล้สุดของคู่ปมของทาร์จาน (Tarjan's off-line least common ancestors algorithm; อันที่จริงแล้ว least ควรจะเป็น lowest) คือขั้นตอนวิธีในการคำนวณหาบรรพบุรุษร่วมต่ำสุด (lowest common ancestors) สำหรับทุก ๆ คู่ของปมในต้นไม้ (rooted tree) โดยมีพื้นฐานในการคำนวณหาจากโครงสร้างข้อมูลที่เรียกว่าโครงสร้างข้อมูลเซตไม่มีส่วนร่วม ขั้นตอนวิธีนี้ได้ถูกตั้งชื่อตาม Robert Tarjan ผู้ซึ่งค้นพบกลวิธีนี้ในปี 1979
ปมบรรพบุรุษร่วมใกล้สุดของระหว่างคู่ปม d และ e ในต้นไม้ T คือ ปม g ซึ่งเป็นปมบรรพบุรุษของทั้งปม d และปม e ที่ไกลจากปมรากมากที่สุด
ขั้นตอนวิธีของทาร์จาน ไม่เหมือนกับขั้นตอนวิธีการหาปมบรรพบุรุษร่วมใกล้สุดของคู่ปมอื่น ๆ  เนื่องจากเป็นขั้นตอนวิธีออฟไลน์ ซึ่งคือขั้นตอนวิธีที่จะต้องป้อนข้อมูลนำเข้าทั้งหมดก่อนเริ่มการแก้ปัญหาตามขั้นตอนวิธี นอกจากนี้ขั้นตอนวิธีของทาร์จาน ยังเป็นขั้นตอนวิธีที่ใช้โครงสร้างข้อมูลที่เรียกว่า การยูเนียนและการค้นหา ทำให้ระยะเวลาที่ใช้สำหรับขั้นตอนวิธีนี้ไม่เป็นค่าคงตัว ในกรณีที่มีจำนวนคู่ของปมเท่ากับจำนวนของปมทั้งหมด ทำให้แตกต่างจากขั้นตอนวิธีอื่น ๆ ที่ไม่ได้ใช้โครงสร้างข้อมูลการยูเนียนและการค้นหา ต่อมาในปี 1983 Gabow และ Tarjan ได้ทำการปรับปรุงประสิทธิภาพของขั้นตอนวิธีให้ใช้ระยะเวลาเร็วขึ้นเป็นแบบเชิงเส้น O(n)
== รหัสเทียม ==
รหัสเทียม ด้านล่างอธิบายถึง ปมบรรพบุรุษร่วมใกล้สุดของแต่ละคู่ปมในต้นไม้ 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
ขั้นตอนวิธี
ขั้นตอนวิธีกราฟ