เรื่อง.. กราฟ ( Graph )
(Graph) เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อนนิยามของกราฟ
กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
(1) โหนด (Nodes) หรือ เวอร์เทกซ์(Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)
- กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนด ถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่า กราฟแบบไม่มีทิศทาง
- ถ้ากราฟมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟว่า กราฟแบบมีทิศทาง บางครั้งเรียกว่า ไดกราฟ
- การเขียนกราฟแสดงโหนดและเส้นเชื่อมความสัมพันธ์ระหว่างโหนดไม่มีรูปแบบที่ตายตัว
- เขียนกราฟเพื่อแสดงให้เห็นความสัมพันธ์ของสิ่งที่สนใจแทนโหนดด้วยจุด (pointes) หรือวงกลม (circles) ที่มีชื่อหรือข้อมูลกำกับ
ลักษณะของกราฟ
- กราฟที่มีลักษณะต่อเนื่อง (Connected) เป็นกราฟที่มีเส้นทางเชื่อมจากโหนดใดๆ ไปยังโหนดอื่นเสมอ
- กราฟที่มีลักษณะเป็นวิถี (Path) มีเส้นเชื่อมไปยังโหนดต่างๆ อย่างเป็นลำดับ โดยแต่ละโหนดจะเป็นโหนดที่ใกล้กันกับโหนดที่อยู่ถัดไป
- กราฟที่เป็นวัฎจักร (Cycle) ต้องมีอย่างน้อย 3 โหนด ที่โหนดสุดท้ายต้องเชื่อมกับโหนดแรก
- กราฟที่มีลักษณะไม่ต่อเนื่อง (Disconnected) ไม่มีเส้นทางเชื่อมจากโหนด 3 ไปยังโหนดอื่นเลย
- กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง (Empty Graph)รูปแบบของกราฟแบบมีทิศทางเหมือนกับรูปแบบของกราฟไม่มีทิศทาง ต่างกันตรงที่กราฟแบนี้จะทิศทางกำกับด้วยเท่านั้น
การแทนกราฟในหน่วยความจำ
สิ่งที่ต้องจัดเก็บ จากกราฟทั่วไป คือ เอ็จ เป็นเส้นเชื่อมระหว่างโหนดสองโหนด มีวิธีเก็บหลายวิธี แต่วิธีที่ง่าย คือ การเก็บเอ็จในแถวลำดับ 2 มิติ แต่จะค่อนข้างเปลืองเนื้องที่ เพราะมีบางเอ็จที่เก็บซ้ำ แก้ไขปัญหานี้โดยใช้แถวลำดับ 2 มิติเก็บโหนด และพอยเตอร์ชี้ไปยังตำแหน่งของโหนดที่สัมพันธ์ และใช้แถวลำดับ 1 มิติเก็บโหนดต่างๆ ที่สัมพันธ์กับโหนดในแถวลำดับ 2 มิติ การใช้วิธีนี้ไม่เหมาะกับกราฟที่มีการเปลี่ยนแปลงตลอดเวลา กราฟที่มีการเปลี่ยนแปลงตลอดเวลาอาจจะใช้วิธีแอดจาเซนซีลิสต์ คล้ายกับวิธีจัดเก็บกราฟแต่ต่างกัยตรงที่ใช้ลิงค์ลิสต์แทนเพื่อความสะดวกในการเปลี่ยนแปลงแก้ไข
การท่องไปในกราฟ (Graph traversal) คือ การเข้าไปเยือนโหนดในกราฟ หลักการทำงาน คือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว
เทคนิคการท่องไปในกราฟมี 2 แบบ คือ
1.การท่องแบบกว้าง (Breadth First Traversal) โดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นที่ละระดับ จนเยือนหมดทุกโหนดในกราฟ (แบบคิว)
2.การท่องแบบลึก (Depth First Traversal) คล้ายกับการท่องทีละระดับของทรี กำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีจนไปสู่ปลายวิถี จากนั้นย้อนกลับ (backtrack) ตามแนววิถีเดิม จนสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่นๆ เพื่อเยือนโหนดอื่นๆ ต่อไปจนครบทุกโหนด (แบบสแตก)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น