ในโลกของการเขียนโปรแกรม, กราฟ (Graph) เป็นโครงสร้างข้อมูลที่มีบทบาทสำคัญยิ่งในการแก้ไขปัญหาหลายๆ อย่าง ไม่ว่าจะเป็นระบบนำทาง, การวิเคราะห์เครือข่ายโซเชียล, หรือแม้กระทั่งในการวางแผนงานที่ซับซ้อน ในบทความนี้เราจะมาสร้างไดเรกเต็ดกราฟ (Directed Graph) ซึ่งเป็นประเภทหนึ่งของกราฟที่ความสัมพันธ์ไม่ใช่สองทาง ด้วยการใช้เมทริกซ์แทนรายการเชื่อมถึง (Adjacency List) ในภาษา Golang กันโดยไม่ต้องพึ่งพิงไลบรารีภายนอก
ก่อนอื่นเลย, มาเริ่มทำความรู้จักกับโครงสร้างข้อมูลที่เรียกว่า "กราฟ" กันก่อน เพื่อเป็นพื้นฐานที่ดีไว้ในการต่อยอดความเข้าใจ
มารู้จักกับ Directed Graph
กราฟประกอบด้วยส่วนที่เรียกว่า 'โหนด' (Node) และ 'เส้นเชื่อม' (Edge) ในกราฟที่เป็น Directed, เส้นเชื่อมจะมีทิศทาง นั่นคือ การเชื่อมจากโหนดหนึ่งไปยังอีกโหนดหนึ่งจะมีความหมายที่ชัดเจนว่ามีทิศทางจาก 'นี้' ไป 'นั่น' ว่าแต่ จะใช้มันอย่างไรในโลกจริง?
Usecase ของ Directed Graph
- ระบบนำทาง: Google Maps คำนวณเส้นทางจากจุด A ไปจุด B โดยใช้ข้อมูลในรูปแบบกราฟเพื่อหาเส้นทางที่ดีที่สุด - การจัดสรรงาน: ในการจัดลำดับการทำงานต่างๆ ภายในโครงการใหญ่ๆ กราฟสามารถช่วยในการวิเคราะห์ขึ้นตอนที่จำเป็นต้องทำก่อนหลัง - เครือข่ายโซเชียล: การวิเคราะห์เครือข่ายโซเชียลด้วยกราฟช่วยในการคำนวณฮับหรือนักอิทธิพลหลักในเครือข่ายลองมาสร้างกราฟเบื้องต้นกับภาษา Golang โดยใช้เมทริกซ์กันเลย!
การใช้เมทริกซ์ในการแทนกราฟ เราจะใช้เมทริกซ์ 2 มิติ เพื่อบอกความสัมพันธ์ระหว่างโหนดต่างๆ นั่นคือ matrix[i][j] = 1 หากมีเส้นเชื่อมจากโหนด i ไปโหนด j และเป็น 0 หากไม่มี
ตัวอย่าง CODE: การสร้าง Directed Graph
อธิบายการทำงาน
1. เราสร้างเมทริกซ์ที่มีขนาดเท่ากับจำนวนโหนด (ในที่นี้คือ 3x3)
2. เราใช้ฟังก์ชัน `addEdge` เพื่อสร้างเส้นเชื่อมระหว่างโหนดต่างๆ
3. พิมพ์เมทริกซ์ที่สร้างได้ ซึ่งจะเห็นความสัมพันธ์ในรูปแบบเลข 1 และ 0
ต่อไปนี้คือสองตัวอย่างเพิ่มเติมที่โชว์ถึงการใช้กราฟในตัวอย่างที่ซับซ้อนขึ้น:
ตัวอย่าง CODE: การค้นหาเส้นทางด้วย DFS (Depth-First Search)
ตัวอย่าง CODE: การค้นหาเส้นทางด้วย BFS (Breadth-First Search)
การสร้างกราฟโดยไม่ใช้ไลบรารี ช่วยให้เราเข้าใจโครงสร้างข้อมูลระดับลึก และช่วยให้เราสามารถปรับแต่งการทำงานของกราฟให้เหมาะสมกับปัญหาที่เราต้องการแก้ไขได้ เช่น อาจจะมีกรณีที่เราต้องการนำเสนอข้อมูลในลักษณะที่ไม่มีในไลบรารีมาตรฐาน หรือต้องการปรับเปลี่ยนลักษณะของเส้นเชื่อมในกราฟในลักษณะที่ไม่ปกติ
ด้วยทักษะเหล่านี้, คุณจะสามารถนำทักษะไปประยุกต์ใช้กับงานในโลกจริงได้อย่างเต็มที่
สนใจเรียนรู้การเขียนโปรแกรมและโครงสร้างข้อมูลอย่างกราฟบ้างไหม? เชิญที่ EPT (Expert-Programming-Tutor) ที่เราสามารถช่วยคุณเข้าใจและใช้งานกราฟเพื่อโจทย์และอุปสรรคต่างๆ ในการพัฒนาซอฟต์แวร์ได้อย่างชำนาญ!
หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM