Minimum Spanning Tree และการประยุกต์ใช้งานด้วยภาษา C

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

#### การใช้ Algorithm ในการค้นหา MST

มีหลาย algorithm ในการหา MST เช่น Kruskal's Algorithm และ Prim's Algorithm ทั้งสองได้รับความนิยมและมีการใช้งานกันอย่างแพร่หลาย สำหรับบทความนี้เราจะใช้ Kruskal's Algorithm เป็นตัวอย่างในการอธิบายและแสดงโค้ดตัวอย่าง

#### Algorithm ของ Kruskal

Kruskal's Algorithm เริ่มต้นด้วยการเรียงลำดับจุดยอดตามน้ำหนักจากน้อยไปหามาก จากนั้นเลือกเส้นที่น้ำหนักน้อยที่สุดในแต่ละครั้งและเพิ่มลงในผลลัพธ์ โดยที่ต้องไม่เกิดการสร้างวงกลมภายในผลลัพธ์ที่เกิดขึ้น วิธีนี้ต้องใช้อุปกรณ์ในการตรวจสอบวงกลมหรือ Cycle Detection เช่น Union-Find Data structure

ต่อไปนี้เป็นตัวอย่างโค้ดโดยใช้ภาษา C:

#include 
#include 

// สร้าง structure สำหรับเส้น (Edge)
typedef struct Edge {
    int src, dest, weight;
} Edge;

// สร้าง structure สำหรับกราฟ
typedef struct Graph {
    int V, E;
    Edge* edge;
} Graph;

// สร้างกราฟที่มีจุดยอด V และเส้น E
Graph* createGraph(int V, int E) {
    Graph* graph = (Graph*) malloc(sizeof(Graph));
    graph->V = V;
    graph->E = E;
    graph->edge = (Edge*) malloc(graph->E * sizeof(Edge));
    return graph;
}

// ฟังก์ชันเปรียบเทียบสำหรับ qsort
int compareEdges(const void* a, const void* b) {
    Edge* e1 = (Edge*)a;
    Edge* e2 = (Edge*)b;
    return e1->weight > e2->weight;
}

เราจำเป็นต้องทำให้กราฟของเราเรียงลำดับเส้นตามน้ำหนักของมันโดยใช้ `qsort` จากไลบรารี `stdlib.h`.

// Union-Find algorithm
int find(int parent[], int i) {
    if (parent[i] == -1)
        return i;
    return find(parent, parent[i]);
}

void Union(int parent[], int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    if(xset != yset) {
       parent[xset] = yset;
    }
}

// ฟังก์ชันหลักสำหรับการหา MST โดยใช้ Kruskal's algorithm
void KruskalMST(Graph* graph) {
    int V = graph->V;
    Edge result[V]; // นี่จะถือ MST
    int e = 0; // ตัวชี้สำหรับ result[]
    int i = 0; // ตัวชี้สำหรับเรียงลำดับเส้น

    // ขั้นตอนแรกคือเรียงลำดับเส้นทั้งหมดตามน้ำหนักของมัน
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), compareEdges);

    // สร้าง parent array สำหรับใช้งานของ union-find
    int *parent = (int*) malloc(V * sizeof(int));
    for (int v = 0; v < V; ++v)
        parent[v] = -1;

    // หมายเลขขอบที่มีน้ำหนักน้อยที่สุดที่ยังไม่รวมอยู่ใน MST
    while (e < V - 1 && i < graph->E) {
        Edge next_edge = graph->edge[i++];

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

        // หากการรวมนี้ไม่ทำให้เกิดวงกลม ค่อยรวมเข้าไปในผลลัพธ์
        if (x != y) {
            result[e++] = next_edge;
            Union(parent, x, y);
        }
    }

    // ส่วนนี้สำหรับการพิมพ์ผลลัพธ์ของ MST
    printf("Following are the edges in the constructed MST\n");
    int minimumCost = 0;
    for (i = 0; i < e; ++i) {
        printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
        minimumCost += result[i].weight;
    }
    printf("Minimum Cost Spanning Tree: %d\n", minimumCost);
    free(parent);
}

หลังจากสร้างฟังก์ชันข้างต้นขึ้นมา เราสามารถใช้ `KruskalMST` ในการหา MST จากกราฟที่มีทั้งหมด

#### Usecase ของ MST ในโลกจริง

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

#### Complexity และข้อดีข้อเสียของ Algorithm

Kruskal's Algorithm มีความซับซ้อนในด้านเวลา (time complexity) อยู่ที่ O(E log E) เนื่องจากขั้นตอนการเรียงลำดับเส้นที่ทำให้เวลาทำงานมีค่าสูงสุด ในขณะเดียวกันหากมีจำนวนเส้นมากขึ้น เวลาที่ใช้ในการเรียงลำดับก็จะเพิ่มขึ้นตามไปด้วย ข้อดีของ Kruskal's Algorithm คือความเรียบง่ายและมีฟังก์ชันที่ชัดเจน สำหรับข้อเสียคืออาจไม่ค่อยเหมาะกับกราฟที่มีจำนวนเส้นมากเนื่องจากการเรียงลำดับทำให้ใช้เวลาทำงานมากขึ้น

#### สรุป

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

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