ประเภทของกราฟในโครงสร้างข้อมูลพร้อมตัวอย่าง

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

กราฟสามารถมีได้หลายประเภท ขึ้นอยู่กับตำแหน่งของโหนดและขอบ ต่อไปนี้เป็นกราฟประเภทที่สำคัญบางส่วน:

กราฟกำกับ

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

นี่คือตัวอย่างของกราฟกำกับ

• เราสามารถไปจากโหนด A ถึง D
• อย่างไรก็ตาม เราไม่สามารถไปจากโหนด D ไปยังโหนด A ได้ เนื่องจากขอบจะชี้จาก A ถึง D
• เนื่องจากกราฟไม่มีน้ำหนัก การเดินทางจากจุดยอด A ถึง D จะมีราคาเท่ากับการเดินทางจาก D ถึง F

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

กราฟที่ไม่มีทิศทางมีขอบที่ไม่มีตัวชี้ หมายความว่าเราสามารถเดินทางกลับกันระหว่างจุดยอดสองจุดได้

นี่คือตัวอย่างง่ายๆ ของกราฟที่ไม่มีทิศทาง

ในกราฟด้านบน

• เราสามารถย้ายจาก A ไป B ได้
• เรายังย้ายจาก B ไป A ได้ด้วย
• ขอบไม่มีทิศทาง

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

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

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

นี่คือตัวอย่างกราฟถ่วงน้ำหนัก (Directed)

• A ไป B มีขอบ และน้ำหนักคือ 5 ซึ่งหมายความว่าการย้ายจาก A ไป B จะทำให้เราใช้เงิน 5
• ชี้ไปที่ B แต่ในกราฟนี้ B ไม่มีขอบเขตตรงเหนือ A ดังนั้นเราจึงเดินทางจาก B ไป A ไม่ได้
• อย่างไรก็ตาม หากเราต้องการย้ายจาก A ไป F ก็มีหลายเส้นทาง เส้นทางคือ ADF, ABF ADF จะมีราคา (10+11) หรือ 21
• ที่นี่ เส้นทาง ABF จะมีราคา (5+15) หรือ 20 ที่นี่เราจะเพิ่มน้ำหนักของแต่ละขอบในเส้นทาง

ต่อไปนี้คือตัวอย่างกราฟแบบไม่มีทิศทางที่มีน้ำหนัก:

ตรงนี้ขอบมีน้ำหนักแต่ไม่มีทิศทาง หมายความว่าการเดินทางจากจุดยอด A ไปยัง D มีค่าใช้จ่าย 10 และในทางกลับกัน

กราฟสองทิศทาง

กราฟสองทิศทางและกราฟไม่มีทิศทางมีคุณสมบัติร่วมกัน นั่นคือ

• โดยทั่วไป กราฟที่ไม่มีทิศทางสามารถมีขอบด้านเดียวระหว่างจุดยอดสองจุดได้

ตัวอย่างเช่น:

• ที่นี่ การย้ายจาก A ไป D หรือ D ไป A จะมีราคา 10
• ในกราฟแบบสองทิศทาง เราสามารถมีขอบสองด้านระหว่างจุดยอดสองจุดได้

นี่คือตัวอย่าง:

การเดินทางจาก A ไป D มีค่าใช้จ่าย 17 บาท แต่การเดินทางจาก D ไปยัง A มีค่าใช้จ่าย 12 บาท ดังนั้นเราจึงไม่สามารถกำหนดน้ำหนักที่แตกต่างกันสองค่าได้หากเป็นกราฟที่ไม่มีทิศทาง

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

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

นี่คือตัวอย่างของกราฟอนันต์:

กราฟว่าง

Null Graph มีเพียงโหนดหรือจุดยอด แต่ไม่มีขอบ หากให้กราฟ G = (V, E) โดยที่ V คือจุดยอดและ E คือขอบ มันจะเป็นโมฆะหากจำนวนขอบ E เป็นศูนย์

นี่คือตัวอย่างของกราฟ Null:

กราฟเล็กน้อย

โครงสร้างข้อมูลกราฟถือเป็นเรื่องเล็กน้อยหากมีจุดยอดหรือโหนดเพียงจุดเดียวโดยไม่มีขอบ

นี่คือตัวอย่างกราฟเล็กน้อย:

มัลติกราฟ

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

นี่คือตัวอย่างของ Multi Graph:

มีขอบสองด้านตั้งแต่ B ถึง A นอกจากนี้ จุดยอด E ยังมีการวนซ้ำในตัวเอง กราฟด้านบนเป็นกราฟกำกับที่ไม่มีน้ำหนักบนขอบ

กราฟที่สมบูรณ์

กราฟจะสมบูรณ์หากจุดยอดแต่ละจุดมีขอบกำกับหรือไม่มีทิศทางกับจุดยอดอื่นๆ ทั้งหมด

สมมติว่ามีจำนวนจุดยอด V ทั้งหมด และแต่ละจุดยอดมีขอบ V-1 พอดี จากนั้นกราฟนี้จะเรียกว่ากราฟที่สมบูรณ์ ในกราฟประเภทนี้ แต่ละจุดยอดจะเชื่อมต่อกับจุดยอดอื่นๆ ทั้งหมดผ่านทางขอบ

นี่คือตัวอย่างกราฟที่สมบูรณ์ซึ่งมีจุดยอด 5 จุด:

คุณสามารถเห็นในภาพว่าจำนวนโหนดทั้งหมดคือห้าโหนด และโหนดทั้งหมดมีสี่ขอบพอดี

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

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

นี่คือตัวอย่างของกราฟที่เชื่อมต่อ:

ต่อไปนี้เป็นคำอธิบายบางส่วนของกราฟ “ตัวอย่างกราฟที่สมบูรณ์” ข้างต้น:

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

กราฟวงจร

กราฟจะเรียกว่าเป็นวงจรหากมีหนึ่งหรือหลายรอบปรากฏอยู่ในกราฟ

นี่คือตัวอย่างของกราฟแบบวน:

ในที่นี้ จุดยอด A, B และ C ก่อตัวเป็นวงจร

กราฟสามารถมีได้หลายรอบอยู่ข้างใน

กราฟ Acyclic แบบกำกับ (DAG)

กราฟเรียกว่า Directed Acyclic Graph หรือ DAG หากไม่มีวงจรภายในกราฟ DAG มีความสำคัญในขณะที่ทำ การเรียงลำดับโทโพโลยี หรือค้นหาคำสั่งดำเนินการ DAG ยังมีความสำคัญสำหรับการสร้างระบบการจัดกำหนดการหรือการสแกนการขึ้นต่อกันของทรัพยากร ฯลฯ อย่างไรก็ตาม กราฟด้านบนไม่มีวงจรใดๆ อยู่ภายใน

นี่คือตัวอย่างง่ายๆ ของ Directed Acyclic Graph (DAG):

กราฟวงจร

กราฟวงจรไม่เหมือนกับกราฟวงจร ใน Cycle Graph แต่ละโหนดจะมีขอบสองอันเชื่อมต่อกันพอดี ซึ่งหมายความว่าแต่ละโหนดจะมีสององศาพอดี

นี่คือตัวอย่างกราฟวงจร:

กราฟทวิภาคี

ประเภทนี้ กราฟ เป็นกราฟชนิดพิเศษที่กำหนดจุดยอดให้กับสองชุด

กราฟทวิภาคีจะต้องเป็นไปตามกฎ:

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

กราฟออยเลอร์

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

นี่คือตัวอย่างกราฟออยเลอร์:

จุดยอดทั้งหมดมีองศาเท่ากัน จุดยอด A, D, E และ H มีองศาสององศา ตรงนี้ โหนด C มีสี่องศา ซึ่งก็คือเลขคู่

แฮมิลตันกราฟ

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

นี่คือตัวอย่างกราฟอย่างง่ายของแฮมิลตัน:

ในภาพนี้ เราสามารถเยี่ยมชมจุดยอดทั้งหมดจากโหนดใดก็ได้ในกราฟด้านบน หนึ่งในเส้นทางที่สามารถเป็นได้ ADCHBE- นอกจากนี้ยังสามารถหา Hamilton Cycle ได้ด้วย Hamilton Cycle เริ่มต้นและสิ้นสุดที่จุดยอดเดียวกัน ดังนั้น วงจรแฮมิลตันจะเป็นเช่นนี้ แอดช์บีอา.