ทำความรู้จักกับ Minimum Spanning Tree ในภาษา Ruby

 

การนำการเขียนโปรแกรมมาใช้ในชีวิตประจำวันสามารถทำให้เรามีเครื่องมือที่ช่วยแก้ปัญหาต่าง ๆ ได้อย่างมีประสิทธิภาพ หนึ่งในปัญหาที่นักคอมพิวเตอร์หลายคนอาจเคยพบคือการตรวจสอบว่า เราจะเชื่อมโยงจุดต่าง ๆ ใน กราฟ (Graph) อย่างไร ให้ได้ผลรวมที่น้อยที่สุด ซึ่งในสถานการณ์นี้เราจะพูดถึงแนวคิดของ Minimum Spanning Tree (MST) และจะเรียนรู้การใช้งานมันในภาษา Ruby

 

Minimum Spanning Tree คืออะไร?

Minimum Spanning Tree (MST) เป็นหนึ่งในโครงสร้างข้อมูลที่สำคัญในทฤษฎีกราฟ โดยเฉพาะอย่างยิ่งเมื่อเราต้องการเชื่อมโยงกราฟในลักษณะที่ไม่มีทางเดินที่ซ้ำกันและมีน้ำหนักรวมที่น้อยที่สุด กล่าวง่าย ๆ ว่า MST คือ กลุ่มของเส้นเชื่อมที่เชื่อมจุดต่าง ๆ ในกราฟให้ครบถ้วนโดยใช้น้ำหนักน้อยที่สุด

ทำไมเราต้องใช้ MST?

MST จะถูกนำไปใช้ในหลายสถานการณ์ เช่น:

- การออกแบบเครือข่าย: ให้เราเชื่อมโยงคอมพิวเตอร์ในองค์กรเพื่อให้ได้การสื่อสารที่เร็วที่สุด

- การค้า: การหาเส้นทางที่ทำให้ขนส่งสินค้าหรือลำเลียงวัตถุดิบต่าง ๆ มีค่าใช้จ่ายต่ำที่สุด

- ด้านสถาปัตยกรรม: ในการวางระบบไฟฟ้า น้ำประปา เพื่อให้เส้นทางการเดินสายมีประสิทธิภาพสูงสุด

 

อัลกอริธึมสำหรับสร้าง MST

มีหลายอัลกอริธึมที่สามารถใช้เพื่อค้นหา MST ได้ เช่น Kruskal's Algorithm และ Prim's Algorithm

1. Kruskal's Algorithm

Kruskal's Algorithm เป็นอัลกอริธึมที่เน้นการใช้เส้นเชื่อมที่มีน้ำหนักน้อยที่สุดในการสร้าง MST โดยเริ่มจากการจัดเรียงเส้นเชื่อมตามน้ำหนักจากน้อยไปมาก

2. Prim's Algorithm

Prim's Algorithm จะเริ่มจากจุดใดจุดหนึ่งในกราฟและเลือกเส้นเชื่อมจากจุดนั้นไปยังจุดอื่น ๆ ที่น้ำหนักน้อยที่สุด จนกว่าทุกจุดจะถูกเชื่อมสัมพันธ์

ในบทความนี้ เราจะนำเสนออัลกอริธึม Kruskal's ด้วยการเขียนโค้ดใน Ruby

 

ตัวอย่างโค้ดในภาษา Ruby

 class Graph
    attr_accessor :vertices, :edges

    def initialize(vertices)
        @vertices = vertices
        @edges = []
    end

    def add_edge(u, v, w)
        @edges << [w, u, v]
    end

    def kruskal_mst
        mst_edges = []
        @edges.sort_by! { |edge| edge[0] } # จัดเรียง edges ตามน้ำหนัก
        parent = {}
        rank = {}

        # ชุดข้อมูลสำหรับ Union-Find
        @vertices.each do |v|
            parent[v] = v
            rank[v] = 0
        end

        # การค้นหา parent
        def find(parent, v)
            parent[v] = find(parent, parent[v]) if parent[v] != v
            parent[v]
        end

        # การรวมกลุ่ม
        def union(parent, rank, u, v)
            root_u = find(parent, u)
            root_v = find(parent, v)

            if root_u != root_v
                if rank[root_u] > rank[root_v]
                    parent[root_v] = root_u
                elsif rank[root_u] < rank[root_v]
                    parent[root_u] = root_v
                else
                    parent[root_v] = root_u
                    rank[root_u] += 1
                end
            end
        end

        @edges.each do |w, u, v|
            if find(parent, u) != find(parent, v)
                mst_edges << [u, v, w]
                union(parent, rank, u, v)
            end
        end

        mst_edges
    end
end

# สร้างกราฟและเพิ่ม edges
g = Graph.new([1, 2, 3, 4])
g.add_edge(1, 2, 1)
g.add_edge(1, 3, 4)
g.add_edge(2, 3, 2)
g.add_edge(2, 4, 7)
g.add_edge(3, 4, 3)

# ค้นหา MST
mst = g.kruskal_mst
puts "Edges in Minimum Spanning Tree:"
mst.each { |u, v, w| puts "#{u} -- #{v} == #{w}" }

ผลการทำงาน

ในโค้ดข้างต้นเราจะเห็นว่าเราได้สร้างกราฟ และเพิ่ม edges ที่ต่างกันเข้าไป แล้วเมื่อเราค้นหา MST เราจะได้เส้นเชื่อมที่มีน้ำหนักน้อยที่สุดเชื่อมกัน ทั้งหมด

 

วิธีวิเคราะห์ Complexity

- เวลา (Time Complexity): O(E log E) เนื่องจากเราต้องจัดเรียงเส้นเชื่อม E ในการค้นหา MST - พื้นที่ (Space Complexity): O(V + E) เมื่อเป็นกราฟที่มี V จุดและ E เส้นเชื่อม

 

ข้อดีและข้อเสียของ Minimum Spanning Tree

ข้อดี

1. ประหยัดทรัพยากร: MST ช่วยให้เราสามารถเชื่อมต่อจุดต่าง ๆ ในกราฟได้อย่างประหยัดค่าใช้จ่าย 2. เพิ่มประสิทธิภาพ: ใช้ในการจัดการกับระบบต่าง ๆ ช่วยเรามองเห็นภาพรวมได้ดีขึ้น

ข้อเสีย

1. ข้อมูลที่คาดไม่ถึง: การทำงานของ MST อาจไม่เหมาะกับกราฟที่มี edge น้ำหนักลบ 2. ซับซ้อน: อาจมีการคำนวนที่ซับซ้อนในกราฟที่มีจำนวน edge มาก ๆ

 

สรุป

Minimum Spanning Tree (MST) เป็นแนวทางที่มีประโยชน์ในการเชื่อมโยงข้อมูลต่าง ๆ โดยไม่สิ้นเปลืองทรัพยากร และแม้ว่าอัลกอริธึมจะมีข้อดีหลายอย่าง แต่ก็ยังต้องคำนึงถึงข้อจำกัดของมันด้วย สำหรับผู้ที่สนใจศึกษาการเขียนโปรแกรมที่เกี่ยวข้องกับกราฟและข้อมูลอื่น ๆ สามารถสมัครเรียนรู้ได้ที่ EPT – Expert Programming Tutor เพื่อพัฒนาทักษะในการเขียนโปรแกรมของคุณกันเถอะ!

การเริ่มต้นเส้นทางการพัฒนาโปรแกรมของคุณครั้งนี้ จะไม่ใช่เรื่องยากอีกต่อไปเมื่อมี EPT คอยให้ความช่วยเหลือให้คุณเติบโตเป็นโปรแกรมเมอร์ที่เชี่ยวชาญในอนาคต!

 

 

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