บทที่ 27 กราฟ DFS และ BFS
จบบทนี้ น้องจะเก็บกราฟแสนจุดลงในโปรแกรมด้วย adjacency list ได้ เดินกราฟด้วย DFS และ BFS ในเวลา O(V + E) นับว่ากราฟแบ่งเป็นกี่กลุ่ม ตอบว่าสองจุดไปถึงกันได้ไหม หาจำนวนก้าวที่น้อยที่สุดพร้อมพิมพ์เส้นทาง หาเกาะและทางออกจากเขาวงกตในตาราง หาจำนวนครั้งที่น้อยที่สุดของปริศนาเทน้ำหรือพลิกของ ตรวจวงจร และแบ่งกราฟเป็นสองฝั่ง โจทย์กราฟที่ไม่มีน้ำหนักเป็นโจทย์ที่ออกบ่อย และชุดทดสอบมักมีกราฟที่ลึกเป็นแสนชั้น บทนี้จึงวัดให้เห็นว่า recursion พังตรงไหน และเขียนแบบที่ไม่พัง
ในบทนี้
| หน้า | ได้อะไร |
|---|---|
| 27.1 กราฟและการเก็บในโปรแกรม | กราฟไม่มีทิศ มีทิศ และมีน้ำหนัก adjacency matrix กับ adjacency list เทียบหน่วยความจำและเวลา |
| 27.2 DFS และส่วนเชื่อมต่อ | DFS แบบ recursion นับส่วนเชื่อมต่อ ตอบว่าถึงกันไหม ความลึกที่ทำให้พัง DFS ด้วย stack ของเราเอง และตรวจวงจร |
| 27.3 BFS และระยะทางที่สั้นที่สุด | ระยะที่สั้นที่สุดบนกราฟไม่มีน้ำหนัก เก็บพ่อเพื่อพิมพ์เส้นทาง BFS หลายจุดเริ่ม และกราฟสองฝั่ง |
| 27.4 DFS และ BFS บนตาราง | เขาวงกต นับเกาะ flood fill ที่ลึกเกิน เทียบกับการจำลองทีละนาที และกับดักจดตอนหยิบออกจาก queue |
| 27.5 BFS บนสถานะ และ 0-1 BFS | ตวงน้ำและพลิกแพนเค้กด้วยจำนวนครั้งที่น้อยที่สุด สถานะที่เป็นสตริง และหัวข้อเสริม 0-1 BFS ด้วย deque |