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

บทนำ

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

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

เรียนรู้วิทยาการข้อมูลเพื่อสร้างความได้เปรียบเหนือคู่แข่งของคุณ

มาดูกราฟประเภทต่างๆ ที่ใช้กันทั่วไปในโครงสร้างข้อมูลและวิธีที่นำไปใช้ในชีวิตจริง

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

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

กราฟ ประเภทต่างๆ ในโครงสร้างข้อมูล สามารถแสดงรายการด้านล่าง:

1. กราฟว่าง

ตามชื่อที่แนะนำ กราฟว่างจะว่างเปล่า มันคือกราฟที่ไม่มีขอบ ประกอบด้วยจุดยอดเดี่ยวในกราฟที่มีชุดขอบว่าง

2. กราฟจำกัด

ถ้าจำนวนขอบและโหนดประกอบด้วยจำนวนจำกัดในกราฟ กราฟนั้นจะเรียกว่ากราฟจำกัด

3. กราฟที่ไม่มีที่สิ้นสุด

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

4. กราฟอย่างง่าย

กราฟได้รับการกล่าวขานว่าเรียบง่ายเมื่อมีเพียงเส้นเชื่อมระหว่างจุดยอดคู่หนึ่ง ดังนั้น โหนดสองโหนดจะเชื่อมต่อกันด้วยขอบด้านหนึ่งของกราฟ ซึ่งสามารถระบุความสัมพันธ์ที่ชัดเจนระหว่างโหนดทั้งสองได้

5. มัลติกราฟ

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

• ขอบขนาน

ขอบที่วิ่งขนานกัน เช่น ถนนคู่ขนานที่วิ่งจากต้นทางหนึ่งไปยังปลายทางเดียวกัน เรียกว่า ขอบขนาน

• ห่วง

นี่คือขอบที่มีจุดยอดต้นทางและปลายทางเหมือนกัน

ตรวจสอบโปรแกรม US - Data Science ของเรา

6. กราฟกำกับ

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

7. กราฟแบบไม่กำหนดทิศทาง

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

8. กราฟที่เชื่อมต่อ

กราฟที่เชื่อมต่อคือกราฟที่มีเส้นทางอย่างน้อยหนึ่งเส้นทางระหว่างโหนดทั้งหมด พูดง่ายๆ ก็คือ หากคุณเริ่มต้นจากโหนดในกราฟที่เชื่อมต่อกัน คุณควรจะสามารถเยี่ยมชมทุกโหนดที่อยู่ในกราฟได้ ดังนั้นควรมีอย่างน้อยหนึ่งเส้นทางสำหรับทุก ๆ โหนด

9. กราฟขาดการเชื่อมต่อ

ในกราฟประเภทนี้ ไม่มีขอบระหว่างคู่ของโหนดหรือจุดยอด ดังนั้น การเข้าถึงโหนดทั้งหมดจากจุดยอดใดๆ นั้นไม่เหมือนกับกราฟที่เชื่อมต่อกัน ถ้าจุดยอดคู่ใดไม่มีเส้นทางระหว่างจุดยอดนั้น เรียกว่า กราฟหลุด

10. ทำกราฟให้สมบูรณ์

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

11. กราฟวงจร

กราฟควรมีองค์ประกอบแบบวงกลมอย่างน้อยหนึ่งองค์ประกอบจึงจะถือว่าเป็นกราฟแบบวงกลม ในทางตรงกันข้าม ถ้ากราฟไม่มีวัฏจักรใดๆ ก็ถือว่าเป็นกราฟอไซคลิก

12. กราฟปกติ

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

13. กราฟสองฝ่าย

เพื่อให้กราฟเป็นแบบสองฝ่าย กราฟควรเป็นไปตามเกณฑ์ต่อไปนี้

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

กราฟที่เป็นไปตามกฎข้างต้นทั้งหมดควรได้รับการพิจารณาว่าเป็นกราฟสองฝ่าย

14. กราฟที่มีป้ายกำกับ

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

15. กำกับกราฟ Acyclic

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

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

การประยุกต์ใช้กราฟที่โดดเด่นที่สุดในวิทยาการคอมพิวเตอร์คือการแสดงการไหลของการคำนวณ กรณีกราฟที่ใช้ที่มีชื่อเสียงอื่น ๆ ได้แก่ :

1. Google แผนที่

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

2. เฟสบุ๊ค

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

3. เวิลด์ไวด์เว็บ

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

4. ระบบปฏิบัติการ

ระบบปฏิบัติการเป็นกรณียอดนิยมของ Resource Allocation Graphs ซึ่งใช้ทุกกระบวนการและทรัพยากรเป็นโหนดหรือจุดยอด ขอบเกิดขึ้นระหว่างทรัพยากรกับกระบวนการจัดสรรหรือจากกระบวนการร้องขอไปยังทรัพยากรที่ร้องขอ บางครั้งวัฏจักรนี้อาจก่อตัวเป็นวงวนไม่สิ้นสุด ซึ่งเป็นการเริ่มต้นการหยุดชะงัก

5. ระบบแผนที่

GPS ของคุณเป็นกรณีกราฟที่ใช้กันอย่างแพร่หลายเพื่อค้นหาร้านอาหาร ร้านค้า และสถานที่ใกล้เคียงที่คุณเลือกที่จะค้นหาด้วยความช่วยเหลือของเทคโนโลยีนี้

6. ไมโครซอฟต์ เอ็กเซล

Directed Acyclic Graphs หรือ DAG ใช้ใน Microsoft Excel

7. อัลกอริทึม Dijkstra

อัลกอริทึม Dijkstra ใช้โครงสร้างข้อมูลกราฟเพื่อระบุเส้นทางที่สั้นที่สุดระหว่างสองโหนด หรือในบางกรณี อาจมากกว่าสองโหนด

8. เครือข่ายการบิน:

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

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

เริ่มต้นการเดินทางของคุณในฐานะนักวิทยาศาสตร์ข้อมูล

หากคุณต้องการเป็นนักวิทยาศาสตร์ข้อมูลและจัดการข้อมูลอย่างมีชั้นเชิงโดยใช้กราฟต่างๆ ที่เราได้เรียนรู้ ลองดูหลักสูตรวิทยาศาสตร์ข้อมูลที่หลากหลายใน upGrad หนึ่งในหลักสูตรที่ได้รับความนิยมมากที่สุดคือหลักสูตร PG-IIITB เกี่ยวกับวิทยาศาสตร์ข้อมูล ซึ่งเป็นหลักสูตรที่ยอดเยี่ยมสำหรับนักวิทยาศาสตร์ข้อมูลมือใหม่ที่กำลังเริ่มต้น!

นี่คือสิ่งที่หลักสูตรนำเสนอ

• การสนับสนุนด้านอาชีพแบบ 360 องศาจากผู้เชี่ยวชาญในอุตสาหกรรมและที่ปรึกษา
• ประสบการณ์จริงกับโครงการอุตสาหกรรมและกรณีศึกษาโดยละเอียดเพื่อวัดความก้าวหน้าอย่างสม่ำเสมอ
• สร้างเครือข่ายกับผู้เชี่ยวชาญด้านวิทยาศาสตร์ข้อมูลทั่วทุกภาคส่วนทั่วโลก

คุณยังสามารถตรวจสอบ หลักสูตร upGrad อื่นๆ ทั้งหมด ใน Data Science