DTS09 - 15-09-52

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