การสำรวจลึก (Depth First Search) ด้วยภาษา Swift

 

 

บทนำ

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

 

อะไรคือ Depth First Search?

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

 

วิธีการทำงานของ DFS

DFS สามารถทำได้โดยการใช้โครงสร้างข้อมูลสองประเภทคือ Stack หรือ Recursive Function ซึ่งในที่นี้เราจะให้คำอธิบายโดยใช้ Recursive Function มากกว่า เนื่องจากภาษา Swift มีคุณสมบัติในการจัดการกับการเรียกฟังก์ชันแบบซ้อนกันได้ดี

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

เรามาเริ่มด้วยการสร้างกราฟเป็นโครงสร้างข้อมูลที่เรียกว่า Dictionary แล้วเราจะสร้างฟังก์ชัน DFS ที่ใช้การเรียกฟังก์ชันกลับ (Recursive) เพื่อแสดงโหนดทั้งหมดในกราฟ

 import Foundation

class Graph {
    var adjList: [String: [String]] = [:]

    func addEdge(from: String, to: String) {
        if adjList[from] == nil {
            adjList[from] = []
        }
        adjList[from]?.append(to)
    }

    func dfs(start: String) {
        var visited: Set<String> = []
        dfsHelper(current: start, visited: &visited)
    }

    private func dfsHelper(current: String, visited: inout Set<String>) {
        visited.insert(current)
        print(current) // แสดงผลโหนดที่ถูกเยี่ยมชม

        guard let neighbors = adjList[current] else { return }

        for neighbor in neighbors {
            if !visited.contains(neighbor) {
                dfsHelper(current: neighbor, visited: &visited)
            }
        }
    }
}

// การใช้งาน
let graph = Graph()
graph.addEdge(from: "A", to: "B")
graph.addEdge(from: "A", to: "C")
graph.addEdge(from: "B", to: "D")
graph.addEdge(from: "C", to: "E")

print("DFS เริ่มต้นที่โหนด A:")
graph.dfs(start: "A")

ในตัวอย่างโค้ดนี้ เรามีการสร้างกราฟที่มีโหนด “A”, “B”, “C”, “D”, “E” และสามารถเชื่อมโยงกันได้ จากนั้นเราบริหารจัดการการค้นหาด้วยการทำการเรียกใช้ฟังก์ชัน `dfs` ที่จะเริ่มต้นการเยี่ยมชมจากโหนด “A”

 

Use Cases ของ DFS ในโลกจริง

Depth First Search มีการใช้งานที่หลากหลายในโลกจริง เช่น:

1. การค้นหาทางในเกม: อัลกอริธึม DFS มักถูกใช้ในการทำ AI สำหรับเกมที่ต้องค้นหาเส้นทางหรือวัตถุภายในแผนที่ 2. การสำรวจข้อมูล: ในกรณีที่ต้องการสำรวจข้อมูลที่มีการเชื่อมโยงกัน สามารถใช้ DFS ในการค้นหาข้อมูลเชิงลึกหรือค้นหา URL เครือข่ายที่เชื่อมโยงกัน 3. การจัดการต้นไม้บันทึก: DFS จะถูกใช้ในการหาแต่ละโหนดหรือบันทึกภายในโครงสร้างที่ตั้งอยู่ในแนวลึก

 

วิเคราะห์ Complexity

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

 

ข้อดีและข้อเสียของ DFS

ข้อดี:

1. ง่ายต่อการเข้าใจและนำไปใช้งาน: วิธีการที่เรียบง่าย ทำให้ DFS สามารถเข้าใจได้ง่าย 2. ใช้พื้นที่น้อยกว่า: สำหรับกราฟที่ลึกแต่แคบ DFS จะใช้พื้นที่น้อยกว่า BFS (Breadth First Search) 3. เหมาะกับกราฟที่มีความหนาแน่นต่ำ: DFS มีประสิทธิภาพดีกว่าเมื่อกราฟมีปริมาณขอบน้อย

ข้อเสีย:

1. สามารถติดอยู่ในเส้นทางที่ไม่สิ้นสุด: ในกรณีของกราฟที่เชื่อมโยงเป็นวงกลม (circular graphs) อาจทำให้เกิดการวนรอบ 2. ไม่สามารถค้นหาเส้นทางที่สั้นที่สุดได้: DFS ไม่พิจารณาว่าสิ่งใดเป็นเส้นทางที่สั้นที่สุด แต่จะค้นหาเพียงเส้นทางที่เข้าสู่โหนดต่อไป 3. ใช้งานได้ช้าในกราฟที่ลึกมาก: อาจเกิดสแต็คโอเวอร์โฟลในกราฟที่มีลึกมาก ๆ

 

สรุป

การสำรวจลึก (DFS) เป็นเทคนิคที่ทรงพลังในการค้นหาในกราฟที่สามารถใช้ได้อย่างมีประสิทธิภาพเมื่อเราเข้าใจวิธีการทำงานและการใช้งานที่หลากหลาย มันมีข้อดีและข้อเสียที่ชัดเจน และต้องมีการใช้งานอย่างเหมาะสมตามประเภทของปัญหาที่เราต้องการแก้ไข

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

 

 

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