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

ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีการหาปมบรรพบุรุษร่วมใกล้สุดของคู่ปมของทาร์จาน (; อันที่จริงแล้ว 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

หมวดหมู่:ขั้นตอนวิธี
หมวดหมู่:ขั้นตอนวิธีกราฟ