บทที่ 9 กราฟ

กราฟ 

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

ประเภท ของกราฟ

มี 2 ประเภท  คือ

1. 1.               กราฟแบบมีทิศทาง

2. 2.               กราฟแบบไม่มีทิศทาง

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

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

เวอร์เท็กซ์ ประชิด (Adjacent Vertex) คือเวอร์เท็กซ์ 2 เวอร์เท็กซ์ที่มีเส้นทางเชื่อมโยงกันหรืออาจเรียกว่าโหนดเพื่อนบ้าน

A   กับ  B   ใช่

C   กับ  F   ไม่ใช่

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

การท่องเข้าไปในกราฟ

1. 1.               การท่องเข้าไปในแนวลึก (Depth - First Traversal)

• Push vertex แรก ลงในสแตก

• เมื่ออยู่ในลูปจะดำเนินการ pop สแตกเพื่อโปรเซสเวอร์เท็กซ์นั้นจากนั้นก็ push เวอร์เท็กซ์ประชิดทุกตัวลงในสแตก

• เมื่อสแตกว่างเปล่าหมายความว่า การท่องเข้า ไปในกราฟได้เสร็จสมบูรณ์

   2. การท่องเข้าไปในแนวกว้าง (Breadth Depth - First Traversal)

• Enqueue vertex แรก ลงในคิว

• เมื่ออยู่ในลูปจะทำการ Dequeue คิวเพ่ออกไปและโปรเซสเวอร์เท็กซ์นั้น จากนั้นก็ดำเนินการนำเวอร์เท็กซ์ปประชิดตัวถัดไปมาไว้ในคิว

• เมื่อคิวว่างเปล่านั้นหมายความ ว่าการท่อง ข้าไปในกราฟได้เสร็จสมบูรณ์