เครื่องกําเนิดเขาวงกตอัลกอริทึมของ Kruskal

อัลกอริทึมของ Kruskal เป็นอัลกอริทึมต้นไม้สแปนนิ่งขั้นต่ําที่สามารถปรับให้เข้ากับการสร้างเขาวงกตได้ มีประสิทธิภาพโดยเฉพาะอย่างยิ่งในการสร้างเขาวงกตที่สมบูรณ์แบบ อีกทางเลือกหนึ่งสําหรับอัลกอริทึมของ Kruskal คืออัลกอริทึมของ Prim ซึ่งเป็นอัลกอริทึมต้นไม้สแปนนิ่งขั้นต่ํา แต่เนื่องจากพวกเขาสร้างเขาวงกตที่เหมือนกันและ Kruskal ทํางานเร็วขึ้นฉันจึงไม่ได้รบกวนการใช้ Prim's

เขาวงกตที่สมบูรณ์แบบคือเขาวงกตที่มีเส้นทางเดียวจากจุดใดก็ได้ในเขาวงกตไปยังจุดใดก็ได้ นั่นหมายความว่าคุณไม่สามารถวนไปวนมาได้ แต่บ่อยครั้งที่คุณจะเจอทางตัน ซึ่งบังคับให้คุณต้องหันหลังกลับและเดินกลับไป

แผนที่เขาวงกตที่สร้างขึ้นที่นี่มีเวอร์ชันเริ่มต้นโดยไม่มีตำแหน่งเริ่มต้นและจุดสิ้นสุด ดังนั้นคุณจึงตัดสินใจเองได้: จะมีทางออกจากจุดใดก็ได้ในเขาวงกตไปยังจุดอื่นๆ หากคุณต้องการแรงบันดาลใจ คุณสามารถเปิดใช้งานตำแหน่งเริ่มต้นและจุดสิ้นสุดที่แนะนำได้ และดูทางออกระหว่างทั้งสองตำแหน่งได้ด้วย

เกี่ยวกับอัลกอริทึมของ Kruskal

อัลกอริทึมของ Kruskal ถูกสร้างขึ้นโดย Joseph Bernard Kruskal, Jr. นักคณิตศาสตร์ นักสถิติ และนักวิทยาศาสตร์คอมพิวเตอร์ชาวอเมริกัน เขาอธิบายอัลกอริทึมครั้งแรกในปี 1956 ในบทความของเขา "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem"

อัลกอริทึมได้รับการออกแบบมาเพื่อค้นหาต้นไม้สแปนซ์ขั้นต่ํา (MST) ของกราฟ เพื่อให้มั่นใจว่าจุดยอดทั้งหมดเชื่อมต่อกับน้ําหนักขอบรวมที่น้อยที่สุดเท่าที่จะเป็นไปได้ในขณะที่หลีกเลี่ยงวัฏจักร

อัลกอริทึมของ Kruskal ทํางานอย่างไรสําหรับการสร้างเขาวงกต

ขั้นตอนที่ 1: เริ่มต้น

• ถือว่าแต่ละเซลล์ในเขาวงกตเป็นชุดแยกต่างหาก (ส่วนประกอบเฉพาะ)
• แสดงรายการผนังทั้งหมดระหว่างเซลล์ที่อยู่ติดกันเป็นขอบที่เป็นไปได้

ขั้นตอนที่ 2: จัดเรียงผนัง

• สับเปลี่ยนหรือสุ่มเรียงลําดับกําแพง หากใช้เป็นอัลกอริทึมของ Kruskal ที่แท้จริง ให้จัดเรียงกําแพงตามลําดับแบบสุ่ม (เนื่องจากการสร้างเขาวงกตไม่ต้องการน้ําหนัก)

ขั้นตอนที่ 3: ผนังกระบวนการ

• ทําซ้ําผ่านกําแพงที่สับเปลี่ยน
• หากเซลล์สองเซลล์ที่หารด้วยผนังเป็นของชุดที่แตกต่างกัน (เช่น ยังไม่ได้เชื่อมต่อในเขาวงกต) ให้ถอดผนังออกและรวมชุด
• หากอยู่ในชุดเดียวกันอยู่แล้ว ให้ข้ามกําแพง (เพื่อหลีกเลี่ยงวงจร)

ขั้นตอนที่ 4: ดําเนินการต่อจนกว่าจะเสร็จสิ้น

• ทําซ้ําขั้นตอนนี้จนกว่าเซลล์ทั้งหมดจะเชื่อมต่อกัน
• ในตอนท้าย ทุกเซลล์จะเชื่อมต่อกับเซลล์อื่นๆ โดยไม่มีลูปหรือส่วนที่แยกจากกัน

เนื่องจากอัลกอริทึมของ Kruskal อาศัยการรวมชุด จึงสามารถปรับให้เหมาะสมได้โดยใช้อัลกอริทึม Union-Find ซึ่งเป็นวิธีที่มีประสิทธิภาพในการติดตามเซลล์ที่เชื่อมต่อระหว่างการสร้างเขาวงกต คุณสามารถดูการใช้งาน PHP ของฉันของอัลกอริทึม Union-Find ได้ที่นี่: Disjoint Set (Union-Find Algorithm) ใน PHP