กราฟในโครงสร้างข้อมูล: ประเภท การจัดเก็บ และการข้ามผ่าน

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

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

ก่อนอื่นเรามาดู กันว่า Graph คืออะไร? เป็นการแสดงข้อมูลในโครงสร้างที่ไม่เป็นเชิงเส้นซึ่งประกอบด้วยโหนด (หรือจุดยอด) และขอบ (หรือเส้นทาง)

กราฟ ในโครงสร้างข้อมูล สามารถเรียกได้ว่าเป็นโครงสร้างข้อมูลที่ประกอบด้วยข้อมูลที่จัดเก็บไว้ในกลุ่มขอบ (เส้นทาง) และจุดยอด (โหนด) หลายกลุ่มซึ่งเชื่อมต่อถึงกัน โครงสร้างข้อมูลกราฟ (N, E) มีโครงสร้างเป็นชุดของโหนดและขอบ ทั้งโหนดและจุดยอดต้องจำกัด

ในการแสดงกราฟด้านบน ชุดของโหนดคือ N={0,1,2,3,4,5,6}และชุดของขอบคือ

ก={01,12,23,34,45,05,03}

ทีนี้มาศึกษาประเภทของกราฟกัน

อ่าน: เทคนิคการสร้างภาพข้อมูล 10 อันดับแรก

ประเภทของกราฟ

1. กราฟถ่วงน้ำหนัก

กราฟที่มีค่าขอบหรือเส้นทาง ค่าทั้งหมดที่เห็นที่เกี่ยวข้องกับขอบเรียกว่าน้ำหนัก ค่าขอบสามารถแทนน้ำหนัก/ต้นทุน/ความยาวได้

ค่าหรือน้ำหนักอาจหมายถึง:

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

2. กราฟไม่ถ่วงน้ำหนัก

ในกรณีที่ไม่มีค่าหรือน้ำหนักที่เกี่ยวข้องกับขอบ ตามค่าเริ่มต้น กราฟทั้งหมดจะไม่ถ่วงน้ำหนัก เว้นแต่จะมีค่าที่เกี่ยวข้อง

3. กราฟไม่มีทิศทาง

เมื่อชุดของวัตถุเชื่อมต่อกัน และขอบทั้งหมดเป็นแบบสองทิศทาง ภาพด้านล่างแสดงกราฟที่ไม่มีทิศทาง

มันเหมือนกับการเชื่อมโยงกันของผู้ใช้ Facebook สองคนหลังจากเชื่อมต่อกันแบบเพื่อน ผู้ใช้ทั้งสองสามารถอ้างอิงและแบ่งปันรูปภาพ แสดงความคิดเห็นระหว่างกันได้

4. กราฟกำกับ

เรียกอีกอย่างว่า digraph ซึ่งชุดของวัตถุ (N, E) เชื่อมต่อกัน และขอบทั้งหมดถูกนำจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง ภาพด้านบนแสดงกราฟกำกับ

ชำระเงิน: โครงการการแสดงข้อมูลที่คุณสามารถทำซ้ำได้

การจัดเก็บกราฟ

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

1. รายการที่อยู่ติดกัน

โหนดในที่นี้จะถูกจัดเก็บเป็นดัชนีของอาร์เรย์แบบมิติเดียว ตามด้วยขอบที่จัดเก็บเป็นรายการ

2. เมทริกซ์ที่อยู่ติดกัน

โหนดในที่นี้แสดงเป็นดัชนีของอาร์เรย์สองมิติ ตามด้วยขอบที่แสดงเป็นค่าที่ไม่ใช่ศูนย์ของเมทริกซ์ที่อยู่ติดกัน

ทั้งแถวและคอลัมน์แสดงโหนด เมทริกซ์ทั้งหมดเต็มไปด้วย "0" หรือ "1" ซึ่งแทนค่าจริงหรือเท็จ ศูนย์แสดงว่าไม่มีเส้นทาง และ 1 หมายถึงเส้นทาง

การข้ามผ่านกราฟ

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

มีโครงสร้างการข้ามผ่านของกราฟสองแบบ

1. DFS (Depth First Search): วิธีค้นหาในเชิงลึก

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

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

ขั้นตอนตามเพื่อใช้การค้นหา DFS:

ขั้นตอนที่ 1 – ต้องกำหนดขนาดสแต็กขึ้นอยู่กับจำนวนโหนดทั้งหมด

ขั้นตอนที่ 2 – เลือกโหนดเริ่มต้นสำหรับแนวขวาง ต้องถูกผลักไปที่สแต็กโดยไปที่โหนดนั้น

ขั้นตอนที่ 3 – ตอนนี้ ไปที่โหนดที่อยู่ติดกันซึ่งไม่เคยเข้าชมมาก่อนแล้วดันไปที่สแต็ก

ขั้นตอนที่ 4 – ทำซ้ำขั้นตอนที่ 3 จนกว่าจะไม่มีโหนดที่อยู่ติดกันที่ไม่ได้เยี่ยมชม

ขั้นตอนที่ 5 – ใช้การย้อนรอยและหนึ่งโหนดเมื่อไม่มีโหนดอื่นให้เยี่ยมชม

ขั้นตอนที่ 6 – ล้างสแต็กโดยทำซ้ำขั้นตอนที่ 3,4 และ 5

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

แอปพลิเคชันของ DFS คือ:

• ไขปริศนาด้วยวิธีเดียวเท่านั้น
• เพื่อทดสอบว่ากราฟเป็นแบบสองส่วนหรือไม่
• Topological Sorting สำหรับจัดตารางงานและอื่นๆ อีกมากมาย

2. BFS (Breadth-First Search): การค้นหาดำเนินการโดยใช้วิธีการเข้าคิว

Breadth-First Search นำทางกราฟในลักษณะวงกว้างและใช้ตามคิวเพื่อข้ามจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง หลังจากพบจุดสิ้นสุดในเส้นทาง

ปฏิบัติตามขั้นตอนเพื่อใช้การค้นหา BFS

ขั้นตอนที่ 1 – ตามจำนวนโหนด คิวถูกกำหนด

ขั้นตอนที่ 2 – เริ่มจากโหนดใดๆ ของการข้ามผ่าน เยี่ยมชมโหนดนั้นและเพิ่มลงในคิว

ขั้นตอนที่ 3 – ตอนนี้ตรวจสอบโหนดที่อยู่ติดกันที่ไม่ได้เยี่ยมชม ซึ่งอยู่หน้าคิว และเพิ่มเข้าไปในคิว ไม่ใช่จุดเริ่มต้น

ขั้นตอนที่ 4 – ตอนนี้ให้เริ่มลบโหนดที่ไม่มีขอบที่จำเป็นต้องเข้าเยี่ยมชมและไม่ได้อยู่ในคิว

ขั้นตอนที่ 5 – ล้างคิวโดยทำซ้ำขั้นตอนที่ 4 และ 5

ขั้นตอนที่ 6 – ลบขอบที่ไม่ได้ใช้และสร้างแผนผังที่ขยายหลังจากคิวว่างเปล่าเท่านั้น

การประยุกต์ใช้ BFS คือ:

• Peer to Peer Networks- เช่นเดียวกับใน Bittorrent จะใช้เพื่อค้นหาโหนดที่อยู่ติดกันทั้งหมด
• โปรแกรมรวบรวมข้อมูลในเครื่องมือค้นหา
• เว็บไซต์โซเชียลเน็ตเวิร์กและอื่น ๆ อีกมากมาย

การประยุกต์ใช้กราฟในโลกแห่งความเป็นจริงในโครงสร้างข้อมูล

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

กราฟในโครงสร้างข้อมูล มีการใช้งานที่หลากหลาย สิ่งที่น่าสังเกตคือ:

• Social Graph APIs – เป็นวิธีหลักในการสื่อสารข้อมูลเข้าและออกจากแพลตฟอร์มโซเชียลมีเดียของ Facebook เป็น API แบบ HTTP ซึ่งใช้ในการสืบค้นข้อมูลโดยทางโปรแกรม อัปโหลดรูปภาพและวิดีโอ สร้างเรื่องราวใหม่ และงานอื่นๆ อีกมากมาย ประกอบด้วยโหนด ขอบ และฟิลด์ ในการสอบถาม จะใช้โหนดอ็อบเจ็กต์เฉพาะ ขอบสำหรับกลุ่มของวัตถุที่อยู่ภายใต้วัตถุเดียว และฟิลด์ใช้เพื่อดึงข้อมูลเกี่ยวกับแต่ละวัตถุในกลุ่ม
• GraphQL API ของ Yelp – เป็นเครื่องมือแนะนำที่ใช้ในการดึงข้อมูลเฉพาะจากแพลตฟอร์ม Yelp ในที่นี้ คำสั่งจะใช้เพื่อค้นหาขอบ หลังจากนั้นระบบจะสอบถามโหนดเฉพาะเพื่อดึงผลลัพธ์ที่แน่นอน ซึ่งจะทำให้กระบวนการดึงข้อมูลเร็วขึ้น

บนแพลตฟอร์ม Yelp โหนดเป็นตัวแทนของธุรกิจ ซึ่งประกอบด้วย id ชื่อ is_closed และคุณสมบัติกราฟอื่นๆ อีกมากมาย

• อัลกอริธึมการปรับเส้นทาง ให้เหมาะสม - ใช้เพื่อค้นหาการเชื่อมต่อที่ดีที่สุดซึ่งเหมาะสมกับเกณฑ์ความเร็ว ความปลอดภัย เชื้อเพลิง ฯลฯ BFS ใช้ในอัลกอริธึมนี้ ตัวอย่างที่ดีที่สุดคือ Google Maps Platform (แผนที่, API เส้นทาง)
• เครือข่าย เที่ยวบิน- ในเครือข่ายการบิน ใช้เพื่อค้นหาเส้นทางที่เหมาะสมที่สุดซึ่งเหมาะกับ โครงสร้าง ข้อมูล กราฟ นอกจากนี้ยังช่วยในรูปแบบและเพิ่มประสิทธิภาพขั้นตอนสนามบินอย่างมีประสิทธิภาพ

อ่านเพิ่มเติม: ประโยชน์ของการสร้างภาพข้อมูล

บทสรุป

ในบทความนี้ ขั้นแรกเราได้กล่าวถึงคำจำกัดความของกราฟและ กราฟในโครงสร้างข้อมูล จากนั้นจึงเรียนรู้เกี่ยวกับประเภทของกราฟด้วยคุณสมบัติของกราฟ ต่อมา เราได้เรียนรู้เกี่ยวกับวิธีการที่ใช้กันทั่วไปในการจัดเก็บกราฟ ตามด้วยวิธีการค้นหาหัวข้อที่สำคัญที่ใช้ใน Graphs, Graph Traversal สุดท้าย เราได้พูดถึงการใช้งานจริงของโครงสร้างข้อมูลกราฟ

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

ทำไมถึงเลือกเรียนกับ upGrad ?

เราขอแนะนำให้คุณเลือก Executive PG Program in Data Science ที่นำเสนอโดย IIIT Bangalore ซึ่งโฮสต์บน upGrad เพราะที่นี่คุณสามารถรับคำถามของคุณ 1-1 กับผู้สอนหลักสูตร ไม่เพียงแค่เน้นการเรียนรู้เชิงทฤษฎีเท่านั้น แต่ยังให้ความสำคัญกับความรู้เชิงปฏิบัติ ซึ่งเป็นสิ่งสำคัญในการเตรียมความพร้อมให้ผู้เรียนพร้อมสำหรับการเผชิญหน้าโครงการในโลกแห่งความเป็นจริง และมอบใบรับรอง NASSCOM ฉบับที่ 1 ของอินเดียแก่คุณ ซึ่งช่วยให้คุณได้งานที่ได้ค่าตอบแทนสูงใน Data Science

ผลงานที่อ้างถึง

ภาควิชาคณิตศาสตร์/CS – หน้าแรก , www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/data-stru.html

“ความรู้ทางคณิตศาสตร์” คำจำกัดความของกราฟกำกับ – Math Insight , mathinsight.org/definition/directed_graph

สิงห์, อมฤตปาล. “โครงสร้างข้อมูลกราฟ” ปานกลาง , ปานกลาง, 29 มี.ค. 2020, medium.com/@singhamritpal49/graph-data-structure-49427c81b3b3

โซโล. “การใช้งานจริงของโครงสร้างข้อมูลกราฟที่คุณต้องรู้จัก” ข้อมูลกราฟและ GraphQL API Development-Leap Graph , leapgraph.com/graph-data-structures-applications