โครงสร้างข้อมูลกราฟและ Algorithms (ตัวอย่าง)
ซาราห์ เฉิน
⚡ สรุปอย่างชาญฉลาด
โครงสร้างข้อมูลกราฟ คือ กลุ่มของจุดยอดและเส้นเชื่อมที่ไม่เป็นเชิงเส้น โดยแต่ละเส้นเชื่อมจะเชื่อมโยงจุดยอดสองจุดเข้าด้วยกัน กราฟใช้จำลองเครือข่ายในโลกแห่งความเป็นจริง เช่น แผนที่ การเชื่อมต่อทางสังคม และเว็บเพจ และสนับสนุนอัลกอริทึมที่มีประสิทธิภาพมากมาย
กราฟในโครงสร้างข้อมูลคืออะไร?
กราฟเป็นโครงสร้างข้อมูลที่ไม่เป็นเชิงเส้น ซึ่งประกอบด้วยจุดยอดและเส้นเชื่อม โดยจุดยอดจะบรรจุข้อมูลหรือข้อมูลต่างๆ และเส้นเชื่อมจะทำหน้าที่เป็นตัวเชื่อมระหว่างจุดยอดสองจุด
กราฟถูกนำมาใช้แก้ปัญหาในโลกแห่งความเป็นจริง เช่น การค้นหาเส้นทางที่ดีที่สุดไปยังจุดหมายปลายทาง และเส้นทางสำหรับการสื่อสารโทรคมนาคมและเครือข่ายสังคม ผู้ใช้ถือเป็นโหนดในกราฟ และเส้นเชื่อมคือขอบที่เชื่อมต่อผู้ใช้เข้าด้วยกัน
ถ้าขอบแสดงเป็น E และจุดยอดแสดงเป็น V ดังนั้นกราฟ G ก็สามารถเขียนเป็นเซตของจุดยอดและขอบได้ เช่น จี (วี, อี).
ตัวอย่างกราฟในโครงสร้างข้อมูล
ต่อไปนี้เป็นตัวอย่างง่ายๆ ของโครงสร้างข้อมูลแบบกราฟ:
นี่คือกราฟแบบไม่มีทิศทางอย่างง่าย (กราฟชนิดหนึ่ง) โดยเซตของจุดยอดคือ {A, B, C, D, E, F} จุดยอดสองจุดเชื่อมต่อกันด้วยเส้นเชื่อม ตัวอย่างเช่น A และ B เชื่อมต่อกันด้วยเส้นเชื่อม แต่ A และ F ไม่ได้เชื่อมต่อกันด้วยเส้นเชื่อมใดๆ
คำศัพท์เฉพาะทางกราฟในโครงสร้างข้อมูล
ต่อไปนี้เป็นคำศัพท์สำคัญบางส่วนที่ใช้ในโครงสร้างข้อมูลกราฟ:
| เทอม | Descriptไอออน |
|---|---|
| จุดสุดยอด | แต่ละองค์ประกอบข้อมูลเรียกว่าจุดยอดหรือโหนด ในภาพด้านบน A, B, C, D และ E คือจุดยอด |
| ขอบ (ส่วนโค้ง) | เส้นเชื่อมระหว่างจุดสองจุดหรือสองจุดยอดเรียกว่า ขอบ (ส่วนโค้ง) โดยจะมีปลายสองข้างและแสดงด้วยรูปแบบ (จุดเริ่มต้น, จุดสิ้นสุด) |
| ขอบที่ไม่ได้กำหนดทิศทาง | มันเป็นขอบสองทิศทาง |
| กำกับขอบ | มันเป็นขอบทิศทางเดียว |
| ขอบถ่วงน้ำหนัก | ขอบที่มีค่ากำกับอยู่ |
| องศา | ในกราฟ จำนวนเส้นขอบที่เชื่อมต่อกับจุดยอดหนึ่งๆ เรียกว่า ดีกรี |
| ระดับปริญญา | จำนวนขอบขาเข้าทั้งหมดที่เชื่อมต่อกับจุดยอด |
| เกินระดับ | จำนวนขอบขาออกทั้งหมดที่เชื่อมต่อกับจุดยอด |
| ห่วงตัวเอง | Edge เรียกว่า self-loop หากจุดปลายทั้งสองตรงกัน |
| ความใกล้เคียง | กล่าวได้ว่าจุดยอดอยู่ติดกันหากมีเส้นขอบเชื่อมระหว่างจุดยอดเหล่านั้น |
ประเภทของกราฟในโครงสร้างข้อมูล
นี่คือรายการที่พบบ่อยที่สุด ประเภทของกราฟในโครงสร้างข้อมูล:
- กราฟกำกับ
- กราฟไม่มีทิศทาง
- กราฟถ่วงน้ำหนัก
- กราฟสองทิศทาง
- กราฟไม่มีที่สิ้นสุด
- กราฟว่าง
- กราฟเล็กน้อย
- มัลติกราฟ
- กราฟที่สมบูรณ์
- กราฟที่เชื่อมต่อ
- กราฟวงจร
- กราฟ Acyclic แบบกำกับ (DAG)
- กราฟวงจร
- กราฟทวิภาคี
- กราฟออยเลอร์
- แฮมิลตันกราฟ
วิธีการแสดงกราฟในโครงสร้างข้อมูล?
โดยทั่วไป กราฟจะถูกจัดเก็บในหน่วยความจำโดยใช้รูปแบบการแสดงผลอย่างใดอย่างหนึ่งจากสองรูปแบบ การเลือกรูปแบบการแสดงผลจะมีผลต่อปริมาณหน่วยความจำที่กราฟใช้และความเร็วในการดำเนินการทั่วไป
- เมทริกซ์ความสัมพันธ์: อาร์เรย์สองมิติขนาด V × V โดยที่เซลล์ [i][j] มีค่าเป็น 1 (หรือน้ำหนักของขอบ) ถ้ามีขอบเชื่อมระหว่างจุดยอด i และจุดยอด j และมีค่าเป็น 0 ในกรณีอื่น ๆ อาร์เรย์นี้ช่วยให้การค้นหาขอบใช้เวลา O(1) แต่ใช้พื้นที่ O(V²) ทำให้เหมาะสำหรับกราฟที่มีความหนาแน่นสูง
- รายการที่อยู่ติดกัน: อาร์เรย์ของลิสต์ที่แต่ละจุดยอดเก็บลิสต์ของจุดยอดข้างเคียง ใช้พื้นที่จัดเก็บข้อมูล O(V + E) และมีประสิทธิภาพสำหรับกราฟแบบเบาบาง ซึ่งเป็นเหตุผลว่าทำไมกราฟในโลกแห่งความเป็นจริงส่วนใหญ่จึงใช้อาร์เรย์นี้
คุณสามารถอ่านข้อมูลเพิ่มเติมเกี่ยวกับเรื่องเหล่านี้ได้ใน รายการประชิดและการแสดงกราฟในรูปแบบเมทริกซ์ เกี่ยวกับการสอน
การประยุกต์โครงสร้างข้อมูลกราฟ
กราฟมีประโยชน์ใช้สอยมากมาย มีอัลกอริธึมหลายอย่างที่ใช้กราฟ ต่อไปนี้คือตัวอย่างการใช้งานกราฟบางส่วน:
- Google แอปแผนที่ใช้กราฟเพื่อหาจุดตัดของถนนสองสายและคำนวณระยะทางระหว่างสองสถานที่ ตัวอย่างเช่น Dijkstraเพื่อค้นหาระยะทางที่สั้นที่สุดระหว่างจุดเริ่มต้นและจุดปลายทาง
- เฟซบุ๊กใช้กราฟเพื่อค้นหาเพื่อนร่วมกันของผู้ใช้ โดยอัลกอริทึมของเฟซบุ๊กจะพิจารณาผู้ใช้แต่ละคนเป็นโหนดในกราฟ
- สำหรับการจัดสรรทรัพยากร จะใช้ DAG (Directed Acyclic Graph) ซึ่งจะตรวจสอบความสัมพันธ์ระหว่างทรัพยากรต่างๆ
- การขอ Google เครื่องมือค้นหาใช้กราฟในการจัดอันดับเว็บไซต์
- แผนที่ping อุปกรณ์นี้ใช้โครงสร้างข้อมูลแบบกราฟ
- A เราเตอร์ และโปรโตคอลของมันใช้กราฟเพื่อเรียนรู้เส้นทางไปยังปลายทาง
