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

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

```text
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

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