# การสร้างกราฟไม่มีทิศทางด้วยตนเองโดยใช้ลิสต์เชื่อมโยงเพื่อแทน adjacency ในภาษา Python
การเขียนโปรแกรมไม่ได้ถูกจำกัดอยู่เพียงแต่กับการสร้างแอปพลิเคชั่นหรือเว็บไซต์เท่านั้น แต่ยังรวมไปถึงการแก้ไขปัญหาทางคณิตศาสตร์และการแสดงข้อมูลในรูปแบบที่เข้าใจง่าย หนึ่งในรูปแบบของข้อมูลที่สำคัญคือ "กราฟ" (Graph) ซึ่งกราฟไม่มีทิศทาง (Undirected Graph) เป็นประเภทหนึ่งที่มีความสำคัญต่อการเข้าใจและการแก้ไขปัญหาในหลาย ๆ สาขา ในบทความนี้ ผมจะแบ่งปันวิธีการสร้างกราฟไม่มีทิศทางด้วยตนเองโดยใช้ลิสต์เชื่อมโยง (Linked List) เพื่อแทน adjacency list ในภาษา Python และจะมีการอธิบายตัวอย่างโค้ดทั้ง 3 ตัวอย่าง พร้อมทั้งนำเสนอ use case ในโลกจริงที่สามารถนำกราฟไปประยุกต์ใช้งานได้
กราฟไม่มีทิศทางคือกราฟที่เชื่อมต่อระหว่างจุดยอด (vertices) ด้วยเส้นเชื่อม (edges) ที่ไม่มีทิศทาง นั้นคือ เส้นเชื่อมต่อระหว่างจุดยอดแต่ละคู่สามารถสัญจรไปมาได้ในทั้งสองทิศทาง
Adjacency List โดยใช้ Linked List
Adjacency List เป็นวิธีหนึ่งในการแทนกราฟ โดยที่เราจะมีรายการหนึ่งรายการสำหรับแต่ละจุดยอด ซึ่งรายการนั้นจะบันทึกข้อมูลเกี่ยวกับจุดยอดอื่นๆ ที่มันเชื่อมต่อด้วย เราสามารถใช้ลิสต์เชื่อมโยงในการเก็บรายการเหล่านี้ เพราะลิสต์เชื่อมโยงสามารถขยายขนาดได้ตามต้องการและสามารถเพิ่มข้อมูลได้อย่างรวดเร็ว
ก่อนที่จะไปถึงตัวอย่างโค้ด มาทำความเข้าใจโครงสร้างของโค้ดกันก่อน
ในโค้ดด้านบน เราได้สร้างคลาส `Node` สำหรับแทนจุดยอด และคลาส `Graph` สำหรับแทนกราฟโดยรวม คลาส `Graph` จะเก็บจุดยอดในรูปของลิสต์เชื่อมโยง (`adjacent`) และดิกชันนารี `vertices` ที่ใช้เก็บคลาส `Node` เพื่อแทนการเชื่อมโยงระหว่างจุดยอด
เพื่อความสมบูรณ์ของโครงสร้างกราฟ เราจำเป็นที่จะต้องเพิ่มฟังก์ชันในการเพิ่มการเชื่อม (edge) และการแสดงกราฟ (display) ดังนั้นโค้ดจะมีลักษณะดังนี้:
ฟังก์ชัน `add_edge` จะรับค่าจุดยอดต้นทาง (`from_vertex`) และจุดยอดปลายทาง (`to_vertex`) และเพิ่มจุดยอดปลายทางเข้าไปในลิสต์เชื่อมโยงของจุดยอดต้นทาง และทำในทางกลับกัน ซึ่งจะเป็นการสร้างเส้นเชื่อมระหว่างจุดยอดทั้งสอง นอกจากนี้ ฟังก์ชัน `display` จะแสดงจุดยอดและจุดยอดที่เชื่อมต่อกับมันในรูปของเอาท์พุทอย่างชัดเจน
เราจะมาดูตัวอย่างการใช้งานคลาส `Graph` ด้วยโค้ด Python ที่จะสาธิตการสร้างกราฟขนาดเล็ก
ตัวอย่างที่ 1: สร้างกราฟและเพิ่มเส้นเชื่อม
เมื่อรันโค้ดข้างต้น คุณจะเห็นเอาท์พุทที่แสดงจุดยอดและเส้นเชื่อมที่เชื่อมต่อกับมัน
ตัวอย่างที่ 2: การตรวจสอบการเชื่อมต่อ
ในตัวอย่างที่สองนี้ เราจะเพิ่มฟังก์ชัน `is_connected` ที่จะตรวจสอบว่ามีเส้นเชื่อมระหว่างจุดยอดทั้งสองหรือไม่
คุณจะเห็นคำตอบว่าจุดยอดที่ 1 และ 2 เป็นส่วนหนึ่งของเส้นเชื่อมเดียวกัน ในขณะที่จุดยอดที่ 3 และ 4 ไม่ได้เชื่อมต่อกับกันและกัน
ตัวอย่างที่ 3: ฟังก์ชันสำหรับการท่องไปในกราฟ
ในตัวอย่างสุดท้าย เราจะเพิ่มฟังก์ชัน `traverse` ที่จะเดินทางผ่านกราฟโดยใช้ค้นหาแบบความกว้าง (Breadth-First Search)
การทำงานของฟังก์ชัน `traverse` จะเริ่มจากจุดยอดเริ่มต้นและทำการเดินทางผ่านกราฟ โดยแสดงผลลัพธ์ออกมาเฉพาะจุดยอดที่ยังไม่ได้เยี่ยมชม
ในโลกจริง กราฟสามารถนำไปใช้ในหลากหลายแอปพลิเคชัน เช่น การหาเส้นทางสั้นที่สุดในระบบเครือข่ายทางหลวง การวิเคราะห์โครงข่ายสังคมออนไลน์ เพื่อจัดกลุ่มผู้คนตามความสนใจร่วมกัน หรือการค้นหาคีย์เวิร์ดที่เกี่ยวข้องกันในการค้นหาข้อมูลบนเว็บไซต์
หวังว่าแนวคิดและวิธีการที่ผมได้นำเสนอนี้ จะเป็นการสร้างแรงบันดาลใจให้คุณเข้ามาศึกษาโลกของการเขียนโปรแกรมที่โรงเรียนการเขียนโปรแกรม EPT พร้อมกับเปิดประตูสู่โลกข้อมูลและแอลกอริทึมในรูปแบบใหม่ ไม่ว่าคุณจะต้องการปรับใช้กราฟในงานวิจัย หรือพัฒนาซอฟต์แวร์ที่ทันสมัย ความรู้พื้นฐานเกี่ยวกับกราฟนั้นมีความสำคัญมาก และเป็นหัวใจสำคัญของหลักสูตรที่ EPT เรามีความกระตือรือร้นที่จะช่วยคุณทำความเข้าใจในหัวข้อนี้และยกระดับทักษะการเขียนโปรแกรมของคุณให้ไปอีกระดับ!
หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM