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

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

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

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

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

อัลกอริทึมของ 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 ซึ่งเป็นวิธีที่มีประสิทธิภาพในการติดตามเซลล์ที่เชื่อมต่อกันระหว่างการสร้างเขาวงกต คุณสามารถดูการใช้งานอัลกอริธึม Union-Find ใน PHP ของฉันได้ที่นี่: [ลิงก์]

อ่านเพิ่มเติม

หากคุณชอบโพสต์นี้ คุณอาจชอบคำแนะนำเหล่านี้ด้วย:

• ล่าและฆ่าเครื่องกําเนิดเขาวงกต
• เครื่องกําเนิดเขาวงกตอัลกอริทึมของวิลสัน
• ตัวสร้างเขาวงกตต้นไม้ที่เติบโต