เรื่อง Graph
กราฟ (Graph) เป็นโครงสร้างข้อมูล แบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็น โครงสร้างข้อมูลที่มีการนำไปใช้ ในงาน ที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน เช่น การวางข่าย งานคอมพิวเตอร์ การ วิเคราะห์เส้นทาง วิกฤติ และปัญหาเส้นทาง ที่สั้นที่สุด
นิยามของกราฟ
กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น ที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
(1) โหนด (Nodes) หรือ เวอร์เทกซ์ (Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)
การเขียนกราฟแสดงโหนดและเส้นเชื่อม ความสัมพันธ์ระหว่างโหนดไม่มีรูปแบบที่ตายตัว การลากเส้นความสัมพันธ์เป็นเส้นลักษณะไหนก็ ได้ที่สามารถแสดงความสัมพันธ์ระหว่างโหนด ได้ถูกต้อง นอกจากนี้เอ็จจากโหนดใด ๆ สามารถ วนเข้าหาตัวมันเองได้
กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัด ของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนด หรือเอ็จเลยเป็นกราฟว่าง (Empty Graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด หรือ เชื่อมตัวเอง เอ็จไม่มีทิศทางกำกับ ลำดับของการ เชื่อมต่อกันไม่สำคัญ นั่นคือไม่มีโหนดใดเป็น โหนดแรก (First Node) หรือไม่มีโหนด เริ่มต้น และไม่มีโหนดใดเป็นโหนดสิ้นสุด
การแทนกราฟในหน่วยความจำ
กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนด และเอ็จโดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็น กราฟว่าง(Empty Graph) แต่ละเอ็จจะเชื่อม ระหว่างโหนดสองโหนด เอ็จมีทิศทางกำกับแสดง ลำดับของการเชื่อมต่อกัน โดยมีโหนดเริ่มต้น (Source Node) และ โหนดสิ้นสุด (Target Node) รูปแบบต่าง ๆ ของกราฟแบบมีทิศทางเหมือนกับ รูปแบบ ของกราฟไม่มีทิศทาง ต่างกันตรงที่กราฟ แบบนี้จะมีทิศทางกำกับด้วยเท่านั้น
การแทนกราฟในหน่วยความจำ ในการปฏิบัติการกับโครงสร้างกราฟ สิ่งที่ ต้องการจัดเก็บจากกราฟโดยทั่วไปก็คือ เอ็จ ซึ่ง เป็นเส้นเชื่อมระหว่างโหนดสองโหนด มีวิธีการ จัดเก็บหลายวิธี วิธีที่ง่ายและตรงไปตรงมา ที่สุดคือ การเก็บเอ็จในแถวลำดับ 2 มิติ
การท่องไปในกราฟ
การท่องไปในกราฟ (graph traversal) คือ กระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการ ทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับ การท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียว แต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้น เพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำ เครื่องหมายบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้ว เพื่อไม่ให้เข้าไปเยือนอีก สำหรับเทคนิคการท่องไป ในกราฟมี 2 แบบดังนี้
1. การท่องแบบกว้าง (Breadth First Traversal)
วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนด อื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุก โหนดในกราฟ ผลลัพธ์จากการท่อง 1 4 6 2 3 8 5 7 9
2. การท่องแบบลึก (Depth First Traversal)
การทำงานคล้ายกับการท่องทีละระดับของทรี โดย กำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตาม แนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น ย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่ง สามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือน โหนดอื่น ๆ ต่อไปจนครบทุกโหนด ผลลัพธ์จาการท่องไปในกราฟ 1 9 6 7 8 5 2 3 4
กราฟ (Graph) เป็นโครงสร้างข้อมูล แบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็น โครงสร้างข้อมูลที่มีการนำไปใช้ ในงาน ที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน เช่น การวางข่าย งานคอมพิวเตอร์ การ วิเคราะห์เส้นทาง วิกฤติ และปัญหาเส้นทาง ที่สั้นที่สุด
นิยามของกราฟ
กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น ที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
(1) โหนด (Nodes) หรือ เวอร์เทกซ์ (Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)
การเขียนกราฟแสดงโหนดและเส้นเชื่อม ความสัมพันธ์ระหว่างโหนดไม่มีรูปแบบที่ตายตัว การลากเส้นความสัมพันธ์เป็นเส้นลักษณะไหนก็ ได้ที่สามารถแสดงความสัมพันธ์ระหว่างโหนด ได้ถูกต้อง นอกจากนี้เอ็จจากโหนดใด ๆ สามารถ วนเข้าหาตัวมันเองได้
กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัด ของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนด หรือเอ็จเลยเป็นกราฟว่าง (Empty Graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด หรือ เชื่อมตัวเอง เอ็จไม่มีทิศทางกำกับ ลำดับของการ เชื่อมต่อกันไม่สำคัญ นั่นคือไม่มีโหนดใดเป็น โหนดแรก (First Node) หรือไม่มีโหนด เริ่มต้น และไม่มีโหนดใดเป็นโหนดสิ้นสุด
การแทนกราฟในหน่วยความจำ
กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนด และเอ็จโดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็น กราฟว่าง(Empty Graph) แต่ละเอ็จจะเชื่อม ระหว่างโหนดสองโหนด เอ็จมีทิศทางกำกับแสดง ลำดับของการเชื่อมต่อกัน โดยมีโหนดเริ่มต้น (Source Node) และ โหนดสิ้นสุด (Target Node) รูปแบบต่าง ๆ ของกราฟแบบมีทิศทางเหมือนกับ รูปแบบ ของกราฟไม่มีทิศทาง ต่างกันตรงที่กราฟ แบบนี้จะมีทิศทางกำกับด้วยเท่านั้น
การแทนกราฟในหน่วยความจำ ในการปฏิบัติการกับโครงสร้างกราฟ สิ่งที่ ต้องการจัดเก็บจากกราฟโดยทั่วไปก็คือ เอ็จ ซึ่ง เป็นเส้นเชื่อมระหว่างโหนดสองโหนด มีวิธีการ จัดเก็บหลายวิธี วิธีที่ง่ายและตรงไปตรงมา ที่สุดคือ การเก็บเอ็จในแถวลำดับ 2 มิติ
การท่องไปในกราฟ
การท่องไปในกราฟ (graph traversal) คือ กระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการ ทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับ การท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียว แต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้น เพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำ เครื่องหมายบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้ว เพื่อไม่ให้เข้าไปเยือนอีก สำหรับเทคนิคการท่องไป ในกราฟมี 2 แบบดังนี้
1. การท่องแบบกว้าง (Breadth First Traversal)
วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนด อื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุก โหนดในกราฟ ผลลัพธ์จากการท่อง 1 4 6 2 3 8 5 7 9
2. การท่องแบบลึก (Depth First Traversal)
การทำงานคล้ายกับการท่องทีละระดับของทรี โดย กำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตาม แนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น ย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่ง สามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือน โหนดอื่น ๆ ต่อไปจนครบทุกโหนด ผลลัพธ์จาการท่องไปในกราฟ 1 9 6 7 8 5 2 3 4
ไม่มีความคิดเห็น:
แสดงความคิดเห็น