สรุปเรื่อง Graph (ต่อ) และ 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+จำนวนโหนดประชิดที่เก็บในคิว
4 ตรวจสอบคิว ถ้ามีข้อมูล ให้ไปทำข้อ 2
5 เลิกงาน
กราฟมีน้ำหนัก หมายถึง กราฟที่ทุกเอดจ์
มีค่าน้ำหนักกำกับ นิยมนำไปใช้แก้ปัญหา
หลัก ๆ 2 ปัญหา คือ
1 การสร้างต้นไม้ทอดข้ามน้อยที่สุด
2 การหาเส้นทางที่สั้นที่สุด
Sorting การเรียงลำดับ
การเรียงลำดับแบบเร็ว
เป็นวิธีที่ใช้เวลาน้อย เหมาะกับข้อมูลที่มีจำนวนมาก
โดยจะเลือกข้อมูลมาหนึ่งค่ามาเป็นค่าหลัก
ถ้าเป็นการเรียงจากค่าน้อยไปหาค่ามากทำการเปรียบเทียบจาก
ตำแหน่งท้ายไปเรื่อย ๆ จนเจอค่าที่น้อยกว่าค่าหลัก
แล้วทำการสลับตำแหน่งกัน หลังจากสลับตำแหน่งให้นำค่าหลัก
เปรียบเทียบกับข้อมูลตำแหน่งที่ 2,3 จนพบข้อมูลที่มีค่ามากกว่า
ค่าหลักแล้วทำการสลับตำแหน่งกัน
การเรียงลำดับแบบแทรก
เป็นวิธีที่ทำการเพิ่มสมาชิกใหม่เข้าไปในเซต
โดยทำการเปรียบเทียบข้อมูลในเซต กับข้อมูลที่ต้องการแทรก
ถ้าเรียงจากค่าน้อยไปหาค่ามาก จะต้องให้ข้อมูล
ที่มีค่าน้อยอยู่ก่อนหน้าข้อมูลที่มีค่ามาก
ไม่มีความคิดเห็น:
แสดงความคิดเห็น