การสำรวจลึกด้วย Depth First Search (DFS) ในภาษา Objective-C

 

การเรียนรู้แนวคิดพื้นฐานเกี่ยวกับการสำรวจกราฟ (Graph Traversal) เป็นเรื่องสำคัญในการศึกษาอัลกอริธึม (Algorithm) ที่จะช่วยให้เราแก้ปัญหาต่างๆ ได้อย่างมีประสิทธิภาพ โดยวันนี้เราจะมาทำความรู้จักกับอัลกอริธึมที่ชื่อว่า Depth First Search (DFS) ซึ่งเป็นเทคนิคที่ใช้ในการค้นหาและสำรวจโครงสร้างข้อมูลแบบกราฟหรือย่อยเชิงลึก (Tree) ที่มีความนิยมและใช้งานอย่างแพร่หลาย

 

Depth First Search คืออะไร

Depth First Search (DFS) เป็นอัลกอริธึมในการค้นหาที่เริ่มต้นจากโหนด (Node) แรก จากนั้นจะไปยังโหนดถัดไปโดยสำรวจให้ลึกที่สุดก่อนที่จะย้อนกลับ เมื่อพบโหนดที่ไม่มีลูกข่าย (Child) หรือเชื่อมต่ออื่นๆ ให้กลับมาที่โหนดก่อนหน้า เพื่อสำรวจเงื่อนไขที่ไม่เคยสำรวจมาก่อน

การใช้อัลกอริธึม DFS

DFS สามารถนำไปใช้แก้ปัญหาต่างๆ ได้มากมาย เช่น:

1. ค้นหาทางเชื่อมในกราฟ: เช่น การตรวจสอบว่ามีเส้นทางระหว่างจุด A และ B หรือไม่ 2. การอยู่ในเกม: หาจุดที่สามารถเดินไปสู่จุดที่ต้องการ เช่น ในเกมกระดาน 3. การหาค่าผลลัพธ์: เช่น การหาควาลู่ของข้อมูลในข้อมูลเชิงลึก เช่น การแสดงข้อมูลในรูปแบบของ Tree

 

ตัวอย่างโค้ด DFS ในภาษา Objective-C

มาดูตัวอย่างโค้ดเพื่อทำความเข้าใจเกี่ยวกับ DFS ในภาษา Objective-C กันดีกว่า:

 #import <Foundation/Foundation.h>

@interface Graph : NSObject
@property (nonatomic, strong) NSMutableDictionary<NSString *, NSMutableArray<NSString *> *> *adjacencyList;
- (void)addEdge:(NSString *)source withDestination:(NSString *)destination;
- (void)depthFirstSearch:(NSString *)startNode;
@end

@implementation Graph

- (instancetype)init {
    self = [super init];
    if (self) {
        self.adjacencyList = [[NSMutableDictionary alloc] init];
    }
    return self;
}

- (void)addEdge:(NSString *)source withDestination:(NSString *)destination {
    if (!self.adjacencyList[source]) {
        self.adjacencyList[source] = [[NSMutableArray alloc] init];
    }
    [self.adjacencyList[source] addObject:destination];
}

- (void)depthFirstSearch:(NSString *)startNode {
    NSMutableSet *visitedNodes = [[NSMutableSet alloc] init];
    [self dfsUtil:startNode visited:visitedNodes];
}

- (void)dfsUtil:(NSString *)currentNode visited:(NSMutableSet *)visitedNodes {
    if (![visitedNodes containsObject:currentNode]) {
        NSLog(@"Visited: %@", currentNode);
        [visitedNodes addObject:currentNode];

        for (NSString *neighbor in self.adjacencyList[currentNode]) {
            [self dfsUtil:neighbor visited:visitedNodes];
        }
    }
}
@end

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        Graph *graph = [[Graph alloc] init];
        [graph addEdge:@"A" withDestination:@"B"];
        [graph addEdge:@"A" withDestination:@"C"];
        [graph addEdge:@"B" withDestination:@"D"];
        [graph addEdge:@"B" withDestination:@"E"];
        [graph addEdge:@"C" withDestination:@"F"];

        NSLog(@"Depth First Search starting from node A:");
        [graph depthFirstSearch:@"A"];
    }
    return 0;
}

การอธิบายโค้ด

- เราเริ่มต้นสร้าง Graph ซึ่งเราจะเก็บเวกเตอร์ (Vector) ของแต่ละโหนดในอาเรย์ของเชื่อมต่อ (Adjacency List)

- ฟังก์ชัน `addEdge` จะช่วยเพิ่มเส้นทางระหว่างโหนดที่ต้องการ

- ฟังก์ชัน `depthFirstSearch` จะเริ่มการค้นหาจากโหนดเริ่มต้น และใช้ฟังก์ชันกรณี `dfsUtil` เพื่อสำรวจโหนดต่างๆ ที่เชื่อมต่อ

Use Case ในโลกจริง

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

 

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

- เวลาความซับซ้อน (Time Complexity): O(V + E) โดยที่ V คือจำนวนโหนด และ E คือจำนวนเส้นเชื่อมในกราฟ - พื้นที่ความซับซ้อน (Space Complexity): O(V) หรือ O(H) ขึ้นอยู่กับการเก็บข้อมูลใน Stack ของการเรียกซ้อน (Recursive Call)

ข้อดีข้อเสียของ DFS

ข้อดี:

1. ใช้ Memory น้อยกว่าในกรณีของกราฟที่มีความลึกน้อย

2. ใช้งานง่ายและสร้างโค้ดได้รวดเร็ว

ข้อเสีย:

1. หากกราฟมีความลึกสูง อาจเกิด Stack Overflow

2. ไม่รับประกันว่าจะพบเส้นทางสั้นที่สุด

 

สรุป

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

 

 

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