สรุปเรื่อง กราฟ (ต่อ) และ Sorting
การท่องไปในกราฟอัลกอริทึ่มแบบลึกมีดังนี้
1. push โหนดเริ่มต้นไปเก็บในสแตก และปรับ Top
ให้ชี้ที่ตำแหน่งจุดเริ่มต้น
2.pop สมาชิกใหม่ออกจากสแตก 1 จำนวน
ปรับค่า pop ใหม่ดังนี้ top=top-1
3.push โหนดประชิดทั้งหมด ของโหนดที่ pop ครั้งสุดท้าย
ลงสแตกกำหนดโหนดที่จะ push นั้นต้องไม่เคย push ลงในสแตกมาก่อน
และปรับค่า top ใหม่ดังนี้
top=top+จำนวนโหนดประชิดที่ push ลงในสแตก
4.ตรวจสอลข้อมูลถ้ามีให้ไปทำที่ ข้อ 2
5.จบการทำงาน
การท่องไปในกราฟอัลกิริทึ่มแบบกว้าง มีดังนี้
1.นำโหนดเริ่มต้นไปเก็บในคิว และปรับค่า Front และ rear=1
2.นำสมาชิกออกจากคิว 1 จำนวน และปรับค่า
Front ใหม่ดังนี้ front=front+1
3.นำโหนดประชิดของโหนดทั้งหมดที่ตำแหน่ง front ไปเก้บในคิว
โดยโหนดที่จะเข้าคิวนั้นจะต้องไปเคยเก็บไว้ในคิวมาก่อน
และปรับค่า rear ใหม่ดังนี้ rear=rear+1
4.ตรวจสอบคิวถ้ามีข้อมูลให้ไปทำ ข้อ 2
5. จบการทำงาน
กราฟมีน้ำหนักหมายถึง กราฟที่ทุกเอจมีค่าน้ำหนักกำกับ
นิยมนำไปใช้แก้ปัญหา 2 ปัญหา หลักๆ คือ
1.การสร้างต้นไม้ทอดข้ามน้อยที่สุด
2.การหาเส้นทางที่สั้นที่สุด
Sorting คือ การเรียงลำดับ
การเรียงลำดับแบบเร็วเป็นวิธีที่ใช้เวลาน้อย
เหมาะกับข้อมูลที่มีจำนวนมาก
โดยจะเลือข้อมูลมาหนึ่งค่าเพื่อมาเป็นข้อหลัก
ถ้าเป้นการเรียงค่าจากน้อยไปหาค่ามากทำการเปรียบเทียบจากตำแหน่งท้ายไปเรื่อยๆ
จนเจอค่าที่น้อยกว่าค่าหลัก แล้วทำการสลับตำแหน่งกัน
หลังจากสลับตำแหน่งให่นำค่าหลักเปรียบเทียบ
กับข้อมูลตำแหน้งที่ 2,3 จนพบข้อมูลที่มีค่ามากกว่า
ค่าหลักแล้วทำการสลับตำแหน่งกัน
การเรียงลำดับแบบแทรก
เป้นวิธีที่ทำการเพิ่มสมาชิกใหม่เข้าไปในเซต
โดยทำการเปรียบเทียบข้อมูลในเซต กับข้อมูลที่ต้องการแทรก
ถ้าต้องการเรียงจากค่าน้อยไปหาค่ามาก จะต้องให้ข้อมูลที่มีค่าน้อยไปอยู่ก่อนหน้าที่มีค่ามาก
สมัครสมาชิก:
ส่งความคิดเห็น (Atom)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น