โครงสร้างข้อมูลกราฟและ Algorithms (ตัวอย่าง)
กราฟในโครงสร้างข้อมูลคืออะไร?
กราฟคือโครงสร้างข้อมูลที่ไม่เป็นเชิงเส้นซึ่งประกอบด้วยจุดยอดและขอบ โดยที่จุดยอดมีข้อมูลหรือข้อมูล และขอบทำหน้าที่เป็นตัวเชื่อมระหว่างจุดยอดคู่หนึ่ง
ใช้เพื่อแก้ปัญหาคำศัพท์จริงเช่นการค้นหาเส้นทางที่ดีที่สุดไปยังตำแหน่งปลายทางและเส้นทางโทรคมนาคมและโซเชียลเน็ตเวิร์ก ผู้ใช้จะถือเป็นโหนดในกราฟ และสายไฟคือขอบที่เชื่อมต่อผู้ใช้
ถ้าขอบแสดงเป็น E และจุดยอดแสดงเป็น V ดังนั้นกราฟ G ก็สามารถเขียนเป็นเซตของจุดยอดและขอบได้ เช่น G (V, E)
ตัวอย่างกราฟในโครงสร้างข้อมูล
นี่คือตัวอย่างง่ายๆ ของโครงสร้างข้อมูลกราฟ:
มันเป็นกราฟที่ไม่มีทิศทางอย่างง่าย (กราฟประเภทหนึ่ง) เซตของจุดยอดคือ: {A, B, C,D,E,F} จุดยอดสองจุดสร้างขอบ ตัวอย่างเช่น A และ B เชื่อมโยงกับขอบ อย่างไรก็ตาม A และ F ไม่ได้เชื่อมโยงกับขอบใดๆ
คำศัพท์เฉพาะทางกราฟในโครงสร้างข้อมูล
ต่อไปนี้เป็นคำศัพท์สำคัญบางประการที่ใช้ในโครงสร้างข้อมูลกราฟ:
เทอม | Descriptไอออน |
---|---|
จุดสุดยอด | องค์ประกอบข้อมูลทั้งหมดเรียกว่าจุดยอดหรือโหนด ในภาพด้านบน A, B, C, D & E คือจุดยอด |
ขอบ (ส่วนโค้ง) | การเชื่อมโยงระหว่างสองโหนดหรือจุดยอดเรียกว่าขอบ (Arc) มันมีปลายสองด้านและแสดงเป็น (startingVertex, endingVertex) |
ขอบที่ไม่ได้กำหนดทิศทาง | มันเป็นขอบสองทิศทาง |
กำกับขอบ | มันเป็นขอบทิศทางเดียว |
ขอบถ่วงน้ำหนัก | ขอบที่มีคุณค่ากับมัน |
องศา | ในกราฟ จำนวนขอบที่เชื่อมต่อกับจุดยอดเรียกว่าองศา |
ระดับปริญญา | จำนวนขอบขาเข้าทั้งหมดที่เชื่อมต่อกับจุดยอด |
เกินระดับ | จำนวนขอบขาออกทั้งหมดที่เชื่อมต่อกับจุดยอด |
ห่วงตัวเอง | Edge เรียกว่า self-loop หากจุดปลายทั้งสองตรงกัน |
ความใกล้เคียง | กล่าวกันว่าจุดยอดอยู่ติดกันหากมีการเชื่อมต่อขอบเข้าด้วยกัน |
ประเภทของกราฟในโครงสร้างข้อมูล
นี่คือรายการที่พบบ่อยที่สุด ประเภทของกราฟในโครงสร้างข้อมูล:
- กราฟกำกับ
- กราฟไม่มีทิศทาง
- กราฟถ่วงน้ำหนัก
- กราฟสองทิศทาง
- กราฟไม่มีที่สิ้นสุด
- กราฟว่าง
- กราฟเล็กน้อย
- มัลติกราฟ
- กราฟที่สมบูรณ์
- กราฟที่เชื่อมต่อ
- กราฟวงจร
- กราฟ Acyclic แบบกำกับ (DAG)
- กราฟวงจร
- กราฟทวิภาคี
- กราฟออยเลอร์
- แฮมิลตันกราฟ
การประยุกต์โครงสร้างข้อมูลกราฟ
กราฟมีกรณีการใช้งานมากมาย มีอัลกอริทึมจำนวนมากที่ใช้กราฟบ่อยครั้ง ต่อไปนี้คือแอปพลิเคชันบางส่วนของกราฟ:
- Google Maps ใช้กราฟเพื่อค้นหาจุดตัดของถนนสองสายและคำนวณระยะทางระหว่างสถานที่สองแห่ง
ตัวอย่างเช่น Dijkstraเพื่อค้นหาระยะทางที่สั้นที่สุดระหว่างตำแหน่งต้นทางและปลายทาง - Facebook ใช้ Graphs เพื่อค้นหาเพื่อนร่วมกันของผู้ใช้ อัลกอริธึมจะถือว่าผู้ใช้แต่ละคนเป็นโหนดของกราฟ
- สำหรับการจัดสรรทรัพยากร จะใช้ DAG (Direct Acyclic Graph) จะตรวจสอบการพึ่งพาของทรัพยากร
- Google Search Engine ใช้กราฟเพื่อสร้างการจัดอันดับเว็บไซต์
- อุปกรณ์การทำแผนที่ใช้โครงสร้างข้อมูลกราฟ
- เราเตอร์ และโปรโตคอลของ t ใช้กราฟเพื่อเรียนรู้เส้นทางของเส้นทางปลายทาง