การสำรวจ Minimum Spanning Tree (MST) ด้วย Objective-C

 

 

อะไรคือ Minimum Spanning Tree (MST)?

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

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

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

 

อัลกอริธึมของ Minimum Spanning Tree

อัลกอริธึมที่นิยมใช้สำหรับการหาค่า MST ได้แก่:

1. Kruskal's Algorithm: สร้าง MST โดยเลือกเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดก่อน โดยพิจารณาจากการจัดกลุ่มจุด (Union-Find) เพื่อลดความซับซ้อน 2. Prim's Algorithm: เริ่มจากจุดเริ่มต้นหนึ่ง และสร้าง MST โดยการเลือกเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดที่สามารถเชื่อมกับต้นไม้ที่มีอยู่

ในบทความนี้ เราจะเน้นไปที่ Prim's Algorithm และเขียนตัวอย่างโค้ดด้วย Objective-C

 

โค้ดตัวอย่างสำหรับ Prim's Algorithm

 #import <Foundation/Foundation.h>

@interface Edge : NSObject
@property (nonatomic) int weight;
@property (nonatomic) int start;
@property (nonatomic) int end;
@end

@implementation Edge
@end

@interface Graph : NSObject
@property (nonatomic, strong) NSMutableArray<Edge *> *edges;
@property (nonatomic) int vertices;

- (instancetype)initWithVertices:(int)vertices;
- (void)addEdge:(int)start end:(int)end weight:(int)weight;
- (void)primMST;
@end

@implementation Graph

- (instancetype)initWithVertices:(int)vertices {
    self = [super init];
    if (self) {
        self.vertices = vertices;
        self.edges = [NSMutableArray array];
    }
    return self;
}

- (void)addEdge:(int)start end:(int)end weight:(int)weight {
    Edge *edge = [[Edge alloc] init];
    edge.start = start;
    edge.end = end;
    edge.weight = weight;
    [self.edges addObject:edge];
}

- (void)primMST {
    NSMutableArray<NSNumber *> *key = [NSMutableArray arrayWithCapacity:self.vertices];
    NSMutableArray<NSNumber *> *parent = [NSMutableArray arrayWithCapacity:self.vertices];
    NSMutableArray<NSNumber *> *included = [NSMutableArray arrayWithCapacity:self.vertices];

    for (int i = 0; i < self.vertices; i++) {
        key[i] = @(INT_MAX);
        parent[i] = @(-1);
        included[i] = @(NO);
    }

    key[0] = @(0);

    for (int i = 0; i < self.vertices - 1; i++) {
        int minKey = INT_MAX;
        int minIndex;

        for (int j = 0; j < self.vertices; j++) {
            if (![included[j] boolValue] && [key[j] intValue] < minKey) {
                minKey = [key[j] intValue];
                minIndex = j;
            }
        }

        included[minIndex] = @(YES);

        for (Edge *edge in self.edges) {
            if (edge.start == minIndex && ![included[edge.end] boolValue] && edge.weight < [key[edge.end] intValue]) {
                parent[edge.end] = @(minIndex);
                key[edge.end] = @(edge.weight);
            } else if (edge.end == minIndex && ![included[edge.start] boolValue] && edge.weight < [key[edge.start] intValue]) {
                parent[edge.start] = @(minIndex);
                key[edge.start] = @(edge.weight);
            }
        }
    }

    NSLog(@"Edge \tWeight");
    for (int i = 1; i < self.vertices; i++) {
        NSLog(@"%d - %d \t%d", parent[i].intValue, i, key[i].intValue);
    }
}

@end

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        Graph *graph = [[Graph alloc] initWithVertices:5];
        [graph addEdge:0 end:1 weight:2];
        [graph addEdge:0 end:3 weight:6];
        [graph addEdge:1 end:2 weight:3];
        [graph addEdge:1 end:3 weight:8];
        [graph addEdge:1 end:4 weight:5];
        [graph addEdge:2 end:4 weight:7];
        [graph addEdge:3 end:4 weight:9];

        [graph primMST];
    }
    return 0;
}

วิธีการทำงานของโค้ด

1. เราสร้างคลาส `Edge` เพื่อเก็บข้อมูลเส้นเชื่อมต่างๆ

2. คลาส `Graph` จะทำหน้าที่ควบคุมการสร้างกราฟและการหาค่า MST

3. เราเริ่มต้นการหาค่า MST ด้วยการเก็บค่าน้ำหนักในอาเรย์ `key` และสถานะการรวมในอาเรย์ `included`

4. การวนลูปจะเลือกเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดและอัปเดตค่าในอาเรย์

 

Use Cases ในโลกจริง

ใช้ MST ในหลายสถานการณ์ เช่น:

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

 

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

- Complexity ของ Prim's Algorithm: O(E log V) โดยที่ E คือจำนวนเส้นเชื่อมและ V คือจำนวนจุดในกราฟ - Complexity ของ Kruskal's Algorithm: O(E log E) เนื่องจากจะต้องจัดเรียงเส้นเชื่อมทั้งหมดก่อน

 

ข้อดี-ข้อเสียของ Algorithm

ข้อดี

- ประสิทธิภาพสูง: สามารถหาค่า MST ได้อย่างรวดเร็วและแม่นยำ - ใช้งานง่าย: กลไกการทำงานที่ชัดเจนและเข้าใจง่าย

ข้อเสีย

- การจัดการหน่วยความจำ: ต้องใช้หน่วยความจำมากหากกราฟมีจุดมากๆ - ซับซ้อน: อาจจะมีความซับซ้อนเมื่อมีการดำเนินการกับกราฟขนาดใหญ่

 

สรุป

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

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

 

 

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