กราฟ
กราฟ
เป็น โครงสร้างที่ประกอบด้วยกลุ่มของโหนดที่ เรียกว่า เวอร์เท็กซ์ และกลุ่มของเอดจ์ ที่ใช้เชื่อมโยงแสดงความสัมพันธ์ระหว่างเวอร์เท็กซ์
ประเภท ของกราฟ
มี 2 ประเภท คือ
-
1. กราฟแบบมีทิศทาง
-
2. กราฟแบบไม่มีทิศทาง
กราฟ แบบมีทิศทางหรือไดกราฟ เป็นกราฟที่แต่ละเส้นจะมีหัวลกศรชี้ไปยังโหนดปลายทาง โดยเส้นเชื่อมโยระหว่างเวอร์เท็กซ์ในกราฟแบบมีทิศทางจะเรียกว่า อาร์ค
กราฟ แบบไม่มีทิศทาง คือกราฟที่ไม่ระบุทิศทางเส้นที่เชื่อมโยงระหว่างเวอร์เท็กซ์จะไม่มีหัวลูกศร หรือเรียกเส้นนี้ว่า เอดจ์
เวอร์เท็กซ์ ประชิด (Adjacent Vertex) คือเวอร์เท็กซ์ 2 เวอร์เท็กซ์ที่มีเส้นทางเชื่อมโยงกันหรืออาจเรียกว่าโหนดเพื่อนบ้าน
A กับ B ใช่
C กับ F ไม่ใช่
การ ค้นหาเวอร์เท็กซ์ เป็นการท่องเข้าไปในกราฟเพื่อต้องการหาเวอร์เท็กซ์ที่เราต้องการถ้าพบก็จะมี การรีเทิร์ค่ากลับไปแต่ถ้าไม่พบก็จะแสดงข้อความผิดพลาดแจ้งให้ทราบ
การท่องเข้าไปในกราฟ
-
1. การท่องเข้าไปในแนวลึก (Depth - First Traversal)
-
Push vertex แรก ลงในสแตก
-
เมื่ออยู่ในลูปจะดำเนินการ pop สแตกเพื่อโปรเซสเวอร์เท็กซ์นั้นจากนั้นก็ push เวอร์เท็กซ์ประชิดทุกตัวลงในสแตก
-
เมื่อสแตกว่างเปล่าหมายความว่า การท่องเข้า ไปในกราฟได้เสร็จสมบูรณ์
2. การท่องเข้าไปในแนวกว้าง (Breadth Depth - First Traversal)
-
Enqueue vertex แรก ลงในคิว
-
เมื่ออยู่ในลูปจะทำการ Dequeue คิวเพ่ออกไปและโปรเซสเวอร์เท็กซ์นั้น จากนั้นก็ดำเนินการนำเวอร์เท็กซ์ปประชิดตัวถัดไปมาไว้ในคิว
-
เมื่อคิวว่างเปล่านั้นหมายความ ว่าการท่อง ข้าไปในกราฟได้เสร็จสมบูรณ์
