ก่อนอื่นมาดูภาพการบีบอัดสองเส้นทาง:
ชุดสหภาพแรงงานเป็นโครงสร้างข้อมูลที่บอบบางและใช้งานได้จริงซึ่งส่วนใหญ่ใช้เพื่อจัดการกับปัญหาการผสานของชุดที่ไม่ได้ตัดกันบางชุด การใช้งานทั่วไปบางอย่าง ได้แก่ การเชื่อมต่อกราฟย่อยอัลกอริทึม Kruskal สำหรับการค้นหาต้นไม้ที่ทอดน้อยที่สุดและบรรพบุรุษทั่วไปน้อยที่สุด (LCA)
เมื่อใช้และค้นหาชุดก่อนอื่นจะมีชุดของชุดไดนามิกที่แยกจากกัน s = {s 1, s 2, ⋯, s k} ซึ่งโดยทั่วไปใช้จำนวนเต็มเพื่อแสดงองค์ประกอบในชุด
แต่ละชุดอาจมีองค์ประกอบอย่างน้อยหนึ่งอย่างและองค์ประกอบในชุดจะถูกเลือกเป็นตัวแทน มันไม่สำคัญที่จะต้องดูแลองค์ประกอบที่มีอยู่ในแต่ละชุดและไม่สำคัญที่จะดูแลองค์ประกอบที่เลือกเป็นตัวแทน สิ่งที่เราสนใจคือสำหรับองค์ประกอบที่กำหนดเราสามารถค้นหาชุด (การเป็นตัวแทน) ที่องค์ประกอบนี้ตั้งอยู่และรวมชุดที่องค์ประกอบทั้งสองตั้งอยู่และความซับซ้อนของเวลาของการดำเนินการเหล่านี้คงที่
มีการดำเนินการพื้นฐานสามประการสำหรับการตรวจสอบและการรวบรวม:
Makeet (s): สร้างชุดใหม่และชุดค้นหาซึ่งมีชุดองค์ประกอบเดียว
Unionset (x, y): ผสานชุดที่องค์ประกอบ x และองค์ประกอบ y อยู่และต้องการให้ชุดที่ x และ y ตั้งอยู่จะไม่ตัดกันและหากพวกเขาตัดกันพวกเขาจะไม่รวม
ค้นหา (x): ค้นหาตัวแทนของชุดที่องค์ประกอบ x อยู่ การดำเนินการนี้ยังสามารถใช้เพื่อตรวจสอบว่าสององค์ประกอบอยู่ในชุดเดียวกันหรือไม่ เพียงเปรียบเทียบตัวแทนของพวกเขา
แพ็คเกจ com.datastructure.union_find; // สหภาพรุ่นที่ห้าของเรา Unionfind5 {// roin [i] แสดงถึงจำนวนเลเยอร์ของต้นไม้ที่แสดงโดยชุดที่ฝังรากโดย I // ในรหัสที่ตามมา ความลึก. มันเป็นเพียงมาตรฐานสำหรับการเปรียบเทียบอันดับ INT ส่วนตัว []; private int [] ผู้ปกครอง; // parent [i] หมายถึงโหนดพาเรนต์ที่ชี้ไปที่การนับ int ส่วนตัว I-th Element; // จำนวนข้อมูล // ตัวสร้าง UnionFind5 (จำนวน int) {road = new int [count]; parent = new int [count]; this.count = นับ; // การเริ่มต้นแต่ละผู้ปกครอง [i] ชี้ไปที่ตัวเองแสดงให้เห็นว่าแต่ละองค์ประกอบสร้างชุดของตัวเองสำหรับ (int i = 0; i <count; i ++) {parent [i] = i; อันดับ [i] = 1; }} // กระบวนการค้นหาค้นหาหมายเลขที่ตั้งไว้ที่สอดคล้องกับองค์ประกอบ p // o (h) ความซับซ้อน, h คือความสูงของต้นไม้ส่วนตัว int ค้นหา (int p) {ยืนยัน (p> = 0 && p <count); // พา ธ การบีบอัด 1 ในขณะที่ (p! = parent [p]) {parent [p] = parent [parent [parent [p]]; p = ผู้ปกครอง [p]; } return p; // การบีบอัดเส้นทาง 2, อัลกอริทึมแบบเรียกซ้ำ // ถ้า (p! = parent [p]) // parent [p] = find (parent [p]); // return parent [p]; } // ตรวจสอบว่าองค์ประกอบ P และองค์ประกอบ Q อยู่ในความซับซ้อนของชุด // O (h) หรือไม่ h คือความสูงของบูลีนสาธารณะของต้นไม้ที่เชื่อมต่อ (int p, int q) {return find (p) == ค้นหา (q); } // ผสานชุดที่องค์ประกอบ p และองค์ประกอบ Q เป็นของ // o (h) ความซับซ้อน, h คือความสูงของต้นไม้โมฆะสาธารณะสาธารณะ (int p, int q) {int proot = find (p); int qroot = find (q); if (proot == qroot) return; // ตัดสินทิศทางการผสานตามจำนวนองค์ประกอบที่แตกต่างกันในต้นไม้ที่องค์ประกอบทั้งสองอยู่ // ผสานชุดที่มีองค์ประกอบน้อยลงในชุดที่มีองค์ประกอบเพิ่มเติมถ้า (อันดับ [proot] <rowat [qroot]) {parent [proot] = Qroot; } อื่นถ้า (อันดับ [qroot] <อันดับ [proot]) {parent [qroot] = proot; } else {// rank [proot] == อันดับ [qroot] พาเรนต์ [proot] = qroot; อันดับ [Qroot] += 1; // ในเวลานี้ฉันรักษาค่าของอันดับ}}}สรุป
ข้างต้นเป็นคำอธิบายโดยละเอียดทั้งหมดของรหัสการบีบอัดพา ธ ในบทความนี้เกี่ยวกับการใช้งานการเขียนโปรแกรม Java และการรวบรวม ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!