โครงสร้างข้อมูลและอัลกอริทึม: ชุดสรุปเร่งรัด

สรุปสูตร ขั้นตอนวิธีทำที่สำคัญของทุกหัวข้อ และโจทย์ฝึก 6 ข้อ พร้อมเฉลยละเอียดไว้ท้ายเล่ม

โจทย์ใหม่กลับไปที่รายวิชา

ในหน้าต่างพิมพ์ ให้เลือก “บันทึกเป็น PDF” เพื่อเก็บสำเนาไว้ในอุปกรณ์ของคุณ

1สูตรและวิธีทำ

ทฤษฎีกราฟ

เล็มมาการจับมือ
Σ deg(v) = 2|E|
กราฟบริบูรณ์
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
กราฟปรกติ
|E| = n·k/2
ต้นไม้และป่า
|E| = n − 1, |E| = n − c
ใบของต้นไม้
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
ออยเลอร์
วงจร: ดีกรีเป็นคู่ทุกจุดยอด; ทางเดิน: มีดีกรีคี่พอดี 2 จุดยอด
วงจรแฮมิลตันใน Kn
(n − 1)!/2
การปรับค่าของไดก์สตรา
d(v) = min(d(v), d(u) + w(u, v))
วอล์กความยาว L
(Mᴸ)ij

วิธีการ

  1. เขียนดีกรีของทุกจุดยอด ผลบวกของดีกรีเท่ากับสองเท่าของจำนวนเส้นเชื่อม
  2. สำหรับโจทย์ออยเลอร์ ให้ตรวจว่ากราฟเชื่อมโยงกัน และนับจุดยอดที่มีดีกรีคี่
  3. สำหรับต้นไม้ ให้ใช้ว่ามี n − 1 เส้นเชื่อม และเล็มมาการจับมือ
  4. สำหรับไดก์สตรา ให้เก็บตารางระยะทางชั่วคราว และยืนยันจุดยอดที่ยังไม่ยืนยันซึ่งมีค่าน้อยที่สุดในแต่ละรอบ
  5. สำหรับต้นไม้ทอดข้ามค่าน้อยที่สุด ให้เรียงเส้นเชื่อมตามน้ำหนักและข้ามทุกเส้นที่ทำให้เกิดวัฏจักร (ครัสคัล) หรือขยายต้นไม้ต้นเดียวจากจุดยอดเริ่มต้น (พริม)

2โจทย์ฝึก

1.อัลกอริทึมและความซับซ้อนปานกลาง

อัลกอริทึมของ Prim สร้างต้นไม้ทอดข้ามที่น้อยที่สุดอย่างไร

  1. Aลบเส้นเชื่อมที่แพงที่สุดจนไม่เหลือวงจร
  2. Bเรียงเส้นเชื่อมทั้งหมดตามน้ำหนักและเพิ่มทีละเส้น เว้นแต่จะก่อวงจรในป่า
  3. Cรัน BFS และเก็บต้นไม้ BFS ไว้
  4. Dขยายต้นไม้ต้นเดียวจากจุดยอดเริ่มต้น โดยเพิ่มเส้นเชื่อมที่ถูกที่สุดที่ออกจากต้นไม้
2.อัลกอริทึมและความซับซ้อนยาก

กฎละโมบ "หยิบสิ่งของตามลำดับมูลค่าต่อน้ำหนัก" ให้คำตอบเหมาะสมที่สุดเสมอในปัญหา knapsack แบบใด

  1. Aไม่ใช่ทั้งสองแบบ
  2. B0/1 knapsack ซึ่งต้องหยิบสิ่งของทั้งชิ้นเสมอ
  3. Cfractional knapsack ซึ่งแบ่งสิ่งของได้
  4. Dทั้งสองแบบ
3.โครงสร้างข้อมูลปานกลาง

บัฟเฟอร์วงกลม (circular buffer หรือ ring buffer) มักใช้สร้าง

  1. Aการท่องกราฟ
  2. Bคิวขนาดคงที่
  3. Cฟังก์ชันแฮช
  4. Dต้นไม้ค้นหาแบบทวิภาค
4.โครงสร้างข้อมูลยาก

โหนด AVL ไม่สมดุลเพราะต้นไม้ย่อยขวาของลูกซ้ายสูงเกินไป (กรณีซ้าย–ขวา) ใช้วิธีแก้ใด

  1. Aหมุนขวาหนึ่งครั้งที่โหนด
  2. Bหมุนซ้ายที่ลูกซ้าย แล้วหมุนขวาที่โหนด
  3. Cหมุนขวาที่ลูกซ้าย แล้วหมุนซ้ายที่โหนด
  4. Dหมุนซ้ายหนึ่งครั้งที่โหนด
5.ทฤษฎีกราฟปานกลาง

กราฟบริบูรณ์ K8 มีวงจรแฮมิลตันที่แตกต่างกันกี่วงจร H วงจรที่ต่างกันเพียงจุดยอดเริ่มต้นหรือทิศทางนับเป็นวงจรเดียวกัน

K8
H =
6.ทฤษฎีกราฟยาก
1816314178205ABCDEF

ขั้นตอนวิธีของครัสคัลสร้างต้นไม้ทอดข้ามค่าน้อยที่สุด ให้คลิกเส้นเชื่อมที่เพิ่มเป็นเส้นหมายเลข 4 เส้นที่ถูกข้ามไม่นับ

k = 4
  1. 1เส้นเชื่อม AC
  2. 2เส้นเชื่อม BC
  3. 3เส้นเชื่อม BD
  4. 4เส้นเชื่อม CE
  5. 5เส้นเชื่อม DE
  6. 6เส้นเชื่อม DF
  7. 7เส้นเชื่อม EF
  8. 8เส้นเชื่อม BE

3สารละลาย

1.อัลกอริทึมและความซับซ้อน

คำตอบ: D · ขยายต้นไม้ต้นเดียวจากจุดยอดเริ่มต้น โดยเพิ่มเส้นเชื่อมที่ถูกที่สุดที่ออกจากต้นไม้

เหตุผลที่เป็นคำตอบนี้

อัลกอริทึมของ Prim ที่ใช้คิวลำดับความสำคัญของเส้นเชื่อมที่ข้ามขอบเขตทำงานใน O(E log V) เมื่อใช้ฮีปไบนารี

คำตอบ

D · ขยายต้นไม้ต้นเดียวจากจุดยอดเริ่มต้น โดยเพิ่มเส้นเชื่อมที่ถูกที่สุดที่ออกจากต้นไม้
2.อัลกอริทึมและความซับซ้อน

คำตอบ: C · fractional knapsack ซึ่งแบ่งสิ่งของได้

เหตุผลที่เป็นคำตอบนี้

เมื่อแบ่งสิ่งของได้ การเลือกอัตราส่วนดีที่สุดก่อนเหมาะสมที่สุด ใน 0/1 knapsack สิ่งของอัตราส่วนสูงอาจขวางชุดที่ดีกว่า จึงต้องใช้การโปรแกรมพลวัต

คำตอบ

C · fractional knapsack ซึ่งแบ่งสิ่งของได้
3.โครงสร้างข้อมูล

คำตอบ: B · คิวขนาดคงที่

เหตุผลที่เป็นคำตอบนี้

Ring buffer ใช้ดัชนีหัวและท้ายที่วนกลับ ให้ enqueue และ dequeue ใน O(1) ด้วยหน่วยความจำคงที่

คำตอบ

B · คิวขนาดคงที่
4.โครงสร้างข้อมูล

คำตอบ: B · หมุนซ้ายที่ลูกซ้าย แล้วหมุนขวาที่โหนด

เหตุผลที่เป็นคำตอบนี้

การหมุนครั้งแรกเปลี่ยนกรณีซ้าย–ขวาเป็นซ้าย–ซ้าย ซึ่งการหมุนขวาที่โหนดไม่สมดุลแก้ได้

คำตอบ

B · หมุนซ้ายที่ลูกซ้าย แล้วหมุนขวาที่โหนด
5.ทฤษฎีกราฟ

คำตอบ: H = 2520

ออยเลอร์ แฮมิลตัน และต้นไม้: กราฟเชื่อมโยงมีวงจรออยเลอร์ (ผ่านทุกเส้นเชื่อมครั้งเดียวและกลับจุดเริ่มต้น) เมื่อทุกจุดยอดมีดีกรีคู่ และมีทางเดินออยเลอร์ที่ไม่ใช่วงจรเมื่อมีจุดยอดดีกรีคี่พอดีสองจุด ทางเดินนั้นไปจากจุดยอดคี่จุดหนึ่งถึงอีกจุดหนึ่ง วงจรแฮมิลตันผ่านทุกจุดยอดครั้งเดียว Kn มีวงจรแบบนี้ (n − 1)!/2 วงจร ต้นไม้ที่มี n จุดยอดมี n − 1 เส้นเชื่อม และกราฟเชื่อมโยงที่มี m เส้นเชื่อมจะเหลือต้นไม้ทอดข้ามหลังเอาเส้นเชื่อมออก m − n + 1 เส้น

นับ

H = (8 − 1)!/2 = 5040/2 = 2520

คำตอบ

H = 2520
6.ทฤษฎีกราฟ

คำตอบ: เส้นเชื่อม CE

เส้นทางที่สั้นที่สุดและต้นไม้ทอดข้าม: ขั้นตอนวิธีของไดก์สตรายืนยันหนึ่งจุดยอดต่อรอบ: จุดยอดที่ยังไม่ยืนยันซึ่งมีระยะทางชั่วคราวน้อยที่สุด ระยะทางของมันเป็นค่าสุดท้ายแล้ว และเพื่อนบ้าน v ทุกจุดได้ d(v) = min(d(v), d(u) + w(u, v)) ขั้นตอนวิธีของครัสคัลสร้างต้นไม้ทอดข้ามค่าน้อยที่สุดโดยเลือกเส้นเชื่อมจากเบาไปหนักและข้ามเส้นที่ทำให้เกิดวัฏจักร ขั้นตอนวิธีของพริมขยายต้นไม้หนึ่งต้นจากจุดยอดเริ่มต้นโดยเพิ่มเส้นเชื่อมที่เบาที่สุดที่ออกจากต้นไม้เสมอ ต้นไม้ทอดข้ามที่มี n จุดยอดมี n − 1 เส้นเชื่อม

ขั้นตอนวิธีของครัสคัล

1. BD (3)
2. BE (5)
3. DF (8)
4. CE (14)
5. AC (18)

เส้นเชื่อมหมายเลข 4

CE

คำตอบ

เส้นเชื่อม CE

ExamProblems · examproblems.com/courses/data-structures-and-algorithms