การเรียนรู้ต้นไม้ประเภท Minimum Spanning Tree ผ่านภาษา Java

แนะนำ Minimum Spanning Tree (MST)

Minimum Spanning Tree (MST) เป็นหนึ่งในการประยุกต์ใช้งานกราฟ (Graph) ที่มีความสำคัญในวิชาวิทยาการคอมพิวเตอร์และแวดวงอคาเดมิกส์ สำหรับการแก้ปัญหาหลากหลายทางด้าน network design, circuit design และอื่นๆ มันประกอบด้วยเซ็ตของ vertices และ edges ที่เชื่อมโยงกันเพื่อสร้างต้นไม้ที่ครอบคลุมจุดยอดทั้งหมด โดยมีระยะทางรวมที่น้อยที่สุด

การใช้งาน Minimum Spanning Tree

ในการออกแบบเครือข่ายโทรคมนาคม เราต้องการเชื่อมโยงสถานีต่างๆ ด้วยสายสัญญาณให้ครอบคลุมทั้งหมดแต่ใช้สายที่น้อยที่สุด เพื่อลดต้นทุนในการติดตั้ง การใช้ MST จึงช่วยแก้ปัญหานี้ได้

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

มีอัลกอริธึมชื่อดังอย่าง Kruskal’s Algorithm และ Prim’s Algorithm ที่ใช้สำหรับแก้ปัญหานี้

การวิเคราะห์ความซับซ้อน (Complexity)

Kruskal's Algorithm มีความซับซ้อนอยู่ที่ `O(E log E)` หรือ `O(E log V)` สำหรับกราฟที่มี `E` เส้นเชื่อมและ `V` จุดยอด ในขณะที่ Prim’s Algorithm มีความซับซ้อนตั้งแต่ `O(V^2)` ถึง `O(E + log V)` ขึ้นอยู่กับการประยุกต์ใช้งาน data structure

ข้อดีของ MST

1. ช่วยลดต้นทุนในการติดตั้งเครือข่าย

2. ประยุกต์ใช้ได้หลากหลายในวิศวกรรมและวิทยาศาสตร์

ข้อเสียของ MST

1. ไม่เหมาะกับกราฟที่มีน้ำหนักเป็นลบ (Negative Weight)

2. อาจมีความซับซ้อนสูงในกราฟที่มีจำนวนจุดยอดมหาศาล

ตัวอย่าง Code ใน Java สำหรับ Kruskal's Algorithm

import java.util.*;
import java.lang.*;
import java.io.*;

class Graph {
    class Edge implements Comparable {
        int src, dest, weight;
        public int compareTo(Edge compareEdge) {
            return this.weight - compareEdge.weight;
        }
    };

    class Subset {
        int parent, rank;
    };

    int vertices, edges;
    Edge[] edge;

    Graph(int v, int e) {
        vertices = v;
        edges = e;
        edge = new Edge[edges];
        for (int i = 0; i < e; ++i) {
            edge[i] = new Edge();
        }
    }

    int find(Subset subsets[], int i) {
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);
        return subsets[i].parent;
    }

    void Union(Subset subsets[], int x, int y) {
        int xroot = find(subsets, x);
        int yroot = find(subsets, y);
        if (subsets[xroot].rank < subsets[yroot].rank)
            subsets[xroot].parent = yroot;
        else if (subsets[xroot].rank > subsets[yroot].rank)
            subsets[yroot].parent = xroot;
        else {
            subsets[yroot].parent = xroot;
            subsets[xroot].rank++;
        }
    }

    void KruskalMST() {
        Edge result[] = new Edge[vertices];
        int e = 0;
        int i = 0;
        for (i = 0; i < vertices; ++i)
            result[i] = new Edge();

        Arrays.sort(edge);

        Subset subsets[] = new Subset[vertices];
        for (i = 0; i < vertices; ++i)
            subsets[i] = new Subset();

        for (int v = 0; v < vertices; ++v) {
            subsets[v].parent = v;
            subsets[v].rank = 0;
        }

        i = 0;
        while (e < vertices - 1) {
            Edge next_edge = new Edge();
            next_edge = edge[i++];

            int x = find(subsets, next_edge.src);
            int y = find(subsets, next_edge.dest);

            if (x != y) {
                result[e++] = next_edge;
                Union(subsets, x, y);
            }
        }

        // พิมพ์ผลลัพธ์ของ MST ที่ได้
        for (i = 0; i < e; ++i)
            System.out.println(result[i].src + " -- " +
                   result[i].dest + " == " + result[i].weight);
    }
}

public class Main {
    public static void main(String[] args) {
        int V = 4; // จำนวนจุดยอดในกราฟ
        int E = 5; // จำนวนเส้นเชื่อมในกราฟ
        Graph graph = new Graph(V, E);

        // ตัวอย
        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;
        graph.edge[0].weight = 10;

        graph.edge[1].src = 0;
        graph.edge[1].dest = 2;
        graph.edge[1].weight = 6;

        graph.edge[2].src = 0;
        graph.edge[2].dest = 3;
        graph.edge[2].weight = 5;

        graph.edge[3].src = 1;
        graph.edge[3].dest = 3;
        graph.edge[3].weight = 15;

        graph.edge[4].src = 2;
        graph.edge[4].dest = 3;
        graph.edge[4].weight = 4;

        graph.KruskalMST();
    }
}

ในตัวอย่างข้างต้น เราได้สร้างกราฟที่มี 4 จุดยอดและ 5 เส้นเชื่อมและแสดงการทำงานของ Kruskal’s Algorithm ในการหา MST ที่เมื่อรันโปรแกรมแล้วจะได้ผลลัพธ์เป็นชุดเส้นเชื่อมที่มีน้ำหนักรวมน้อยที่สุดสำหรับการเชื่อมต่อทุกจุดยอด

ตัวอย่าง Usecase ในโลกจริง

1. การออกแบบเครือข่ายระบบสาธารณูปโภค เช่น ไฟฟ้า น้ำ และก๊าซ

2. การออกแบบเส้นทางการเดินท่องเที่ยวภายในประเทศหรือเส้นทางเดินป่า

3. การจัดสรรเครือข่ายการสื่อสารในองค์กรหรือโรงงานอุตสาหกรรม

การเรียนรู้เกี่ยวกับ MST ช่วยเพิ่มความเข้าใจต่อหลักสูตรและการประยุกต์ใช้งานในชีวิตจริงได้ หากต้องการเรียนรู้มากขึ้นเกี่ยวกับการใช้งานกราฟและการวิเคราะห์ข้อมูลผ่านโครงสร้างข้อมูล, ขอเชิญทุกท่านมาเรียนรู้ด้าน Programming ที่สถาบัน EPT ซึ่งเรามีหลักสูตรที่จะทำให้คุณเข้าใจพื้นฐานของอัลกอริธึมและการเขียนโค้ดในระดับลึกถึงการประยุกต์ใช้ในการแก้ไขปัญหาทางธุรกิจและวิทยาการคอมพิวเตอร์ได้อย่างมั่นใจและเกิดประโยชน์สูงสุด!

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