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

ระวังสับสนกับ Tarjan's strongly connected components algorithm

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