โครงสร้างข้อมูลกราฟและ Algorithms (ตัวอย่าง)

กราฟในโครงสร้างข้อมูลคืออะไร?

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

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

ถ้าขอบแสดงเป็น E และจุดยอดแสดงเป็น V ดังนั้นกราฟ G ก็สามารถเขียนเป็นเซตของจุดยอดและขอบได้ เช่น G (V, E)

ตัวอย่างกราฟในโครงสร้างข้อมูล

นี่คือตัวอย่างง่ายๆ ของโครงสร้างข้อมูลกราฟ:

มันเป็นกราฟที่ไม่มีทิศทางอย่างง่าย (กราฟประเภทหนึ่ง) เซตของจุดยอดคือ: {A, B, C,D,E,F} จุดยอดสองจุดสร้างขอบ ตัวอย่างเช่น A และ B เชื่อมโยงกับขอบ อย่างไรก็ตาม A และ F ไม่ได้เชื่อมโยงกับขอบใดๆ

คำศัพท์เฉพาะทางกราฟในโครงสร้างข้อมูล

ต่อไปนี้เป็นคำศัพท์สำคัญบางประการที่ใช้ในโครงสร้างข้อมูลกราฟ:

ประเภทของกราฟในโครงสร้างข้อมูล

นี่คือรายการที่พบบ่อยที่สุด ประเภทของกราฟในโครงสร้างข้อมูล:

• กราฟกำกับ
• กราฟไม่มีทิศทาง
• กราฟถ่วงน้ำหนัก
• กราฟสองทิศทาง
• กราฟไม่มีที่สิ้นสุด
• กราฟว่าง
• กราฟเล็กน้อย
• มัลติกราฟ
• กราฟที่สมบูรณ์
• กราฟที่เชื่อมต่อ
• กราฟวงจร
• กราฟ Acyclic แบบกำกับ (DAG)
• กราฟวงจร
• กราฟทวิภาคี
• กราฟออยเลอร์
• แฮมิลตันกราฟ

การประยุกต์โครงสร้างข้อมูลกราฟ

กราฟมีกรณีการใช้งานมากมาย มีอัลกอริทึมจำนวนมากที่ใช้กราฟบ่อยครั้ง ต่อไปนี้คือแอปพลิเคชันบางส่วนของกราฟ:

• Google Maps ใช้กราฟเพื่อค้นหาจุดตัดของถนนสองสายและคำนวณระยะทางระหว่างสถานที่สองแห่ง
  ตัวอย่างเช่น Dijkstraเพื่อค้นหาระยะทางที่สั้นที่สุดระหว่างตำแหน่งต้นทางและปลายทาง
• Facebook ใช้ Graphs เพื่อค้นหาเพื่อนร่วมกันของผู้ใช้ อัลกอริธึมจะถือว่าผู้ใช้แต่ละคนเป็นโหนดของกราฟ
• สำหรับการจัดสรรทรัพยากร จะใช้ DAG (Direct Acyclic Graph) จะตรวจสอบการพึ่งพาของทรัพยากร
• Google Search Engine ใช้กราฟเพื่อสร้างการจัดอันดับเว็บไซต์
• อุปกรณ์การทำแผนที่ใช้โครงสร้างข้อมูลกราฟ
• เราเตอร์ และโปรโตคอลของ t ใช้กราฟเพื่อเรียนรู้เส้นทางของเส้นทางปลายทาง