การท่องไปในกราฟ
การท่องไปในกราฟ คือกระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับการท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียวแต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้น
เพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำเครื่องหมายบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้ว การท่องไปในกราฟมี2แบบคือ
1. การท่องแบบกว้าง วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟ
2. การท่องแบบลึก การทำงานคล้ายกับการท่องทีละระดับของทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตาม
แนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้นย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด
การเรียงลำดับ (sorting)
เป็นการจัดให้เป็นระเบียบมีแบบแผน ช่วยให้การค้นหาสิ่งของหรือข้อมูล ซึ่งจะสามารถกระทำได้รวดเร็วและมีประสิทธิภาพ
การเรียงลำดับอย่างมีประสิทธิภาพ
- เวลาและแรงงานที่ต้องใช้ในการเขียนโปรแกรม
- เวลาที่เครื่องคอมพิวเตอร์ต้องใช้ในการทำงานตามโปรแกรมที่เขียน
- จำนวนเนื้อที่ในหน่วยความจำหลักมีเพียงพอหรือไม่
วิธีการเรียงลำดับ
-การเรียงลำดับแบบภายใน (internal sorting)เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ในหน่วยความจำหลัก เวลาที่ใช้ในการเรียงลำดับจะคำนึงถึงเวลาที่ใช้ในการเปรียบเทียบและเลื่อนข้อมูลภายในความจำหลัก
- การเรียงลำดับแบบภายนอก(external sorting) เป็นการเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำสำรอง ซึ่งเป็นการ
เรียงลำดับข้อมูลในแฟ้มข้อมูล (file) เวลาที่ใช้ในการเรียงลำดับต้องคำนึงถึงเวลาที่เสียไประหว่างการถ่ายเทข้อมูลจากหน่วยความจำหลักและหน่วยความจำสำรองนอกเหนือจากเวลาที่ใช้ในการเรียงลำดับข้อมูลแบบภายใน
1.การเรียงลำดับแบบเลือก (selection sort)
2.การเรียงลำดับแบบฟอง (Bubble Sort)
สมัครสมาชิก:
ส่งความคิดเห็น (Atom)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น