BFS สำหรับพาธสั้นที่สุดแบบไม่มีน้ำหนัก
หาระยะทางจากต้นทางทีละชั้น
BFS สำหรับพาธสั้นที่สุดแบบไม่มีน้ำหนัก เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
BFS ทำอะไร
BFSสำรวจกราฟเป็นชั้น ๆ โดยเริ่มจากจุดเริ่มต้น จากนั้นสำรวจทุกจุดที่อยู่ห่างหนึ่งขั้น แล้วจึงสำรวจจุดที่อยู่ห่างสองขั้น และทำต่อไปเรื่อย ๆ 🌊
เหตุใดการสำรวจเป็นชั้นจึงให้เส้นทางสั้นที่สุด
เนื่องจาก BFS สำรวจแต่ละชั้นเสร็จก่อนเริ่มชั้นถัดไป ครั้งแรกที่ BFS ไปถึงโหนดใด โหนดนั้นจะอยู่บนเส้นทางแบบไม่มีน้ำหนักที่สั้นที่สุดจากจุดเริ่มต้น
คิวคือกลไกหลัก
BFS ใช้คิว ซึ่งมีหลักการเข้าก่อนออกก่อน คุณเพิ่มเพื่อนบ้านใหม่ไว้ด้านหลัง แล้วประมวลผลสมาชิกด้านหน้าถัดไป
from collections import deque
q = deque([start])ติดตามสิ่งที่เยี่ยมชมแล้ว
เก็บเครื่องหมายเยี่ยมชมแล้วไว้ เพื่อไม่ใส่โหนดเดิมลงในคิวซ้ำ วิธีนี้ทำให้ BFS รวดเร็วและจบการทำงานได้แน่นอน
visited = [False] * (n + 1)
visited[start] = Trueเก็บระยะทาง
อาร์เรย์ระยะทางจะเก็บชั้นของแต่ละโหนด จุดเริ่มต้นมีค่า 0 ส่วนเพื่อนบ้านแต่ละตัวจะมีค่ามากกว่าจุดก่อนหน้าหนึ่ง
dist = [-1] * (n + 1)
dist[start] = 0นำสมาชิกด้านหน้าออกด้วย pop
ในแต่ละขั้น ให้นำโหนดที่อยู่ด้านหน้าของคิวออกด้วย pop โหนดนี้เป็นโหนดที่ยังไม่ได้ประมวลผลและอยู่ใกล้ที่สุด จึงควรจัดการตอนนี้
u = q.popleft()ขยายไปยังเพื่อนบ้าน
สำหรับเพื่อนบ้านแต่ละตัวของ u ที่ยังไม่เคยเยี่ยมชม ให้ทำเครื่องหมาย กำหนดระยะทาง แล้วใส่ลงด้านหลังของคิว
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)ลูปฉบับเต็ม
นำสมาชิกออกและขยายไปยังเพื่อนบ้านต่อไปขณะที่คิวยังไม่ว่าง เมื่อคิวหมดลง คุณจะเยี่ยมชมโหนดทุกโหนดที่ไปถึงได้แล้ว
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)ทำเครื่องหมายตอนใส่คิว
กำหนดค่าเยี่ยมชมแล้วทันทีที่ใส่โหนดลงในคิว ไม่ใช่ตอนนำออก การทำเครื่องหมายล่าช้าจะทำให้โหนดซ้ำหลุดเข้าไปในคิวได้
โหนดที่ไปไม่ถึงจะยังมีค่า -1
โหนดใดก็ตามที่ยังมีระยะทางเป็น -1 หลังจาก BFS จบ แสดงว่าโหนดนั้นไปไม่ถึงจากจุดเริ่มต้นของคุณ คำตอบเช่นนี้ก็มีความหมายเช่นกัน
BFS มีความซับซ้อนเชิงเส้น
BFS แตะโหนดและเส้นเชื่อมแต่ละรายการเพียงครั้งเดียว จึงทำงานในเวลา O(n + m) ซึ่งเพียงพอสำหรับข้อจำกัดของการแข่งขันส่วนใหญ่
ตรวจสอบอย่างรวดเร็ว
เหตุใด BFS แบบธรรมดาจึงให้เส้นทางสั้นที่สุด
ทบทวน
คุณใช้ BFS ร่วมกับคิวและอาร์เรย์ระยะทาง โดยทำเครื่องหมายตอนใส่คิว ขยายไปยังเพื่อนบ้าน และอ่านระยะทางสั้นที่สุดเมื่อการทำงานจบลง 🎉
คำถามที่พบบ่อย
บทเรียน “BFS สำหรับพาธสั้นที่สุดแบบไม่มีน้ำหนัก” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “BFS สำหรับพาธสั้นที่สุดแบบไม่มีน้ำหนัก” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “BFS สำหรับพาธสั้นที่สุดแบบไม่มีน้ำหนัก”
หาระยะทางจากต้นทางทีละชั้น คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน
บทเรียน “BFS สำหรับพาธสั้นที่สุดแบบไม่มีน้ำหนัก” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- สร้างรายการประชิดจากข้อมูลเข้า
- BFS สำหรับพาธสั้นที่สุดแบบไม่มีน้ำหนัก
- DFS การเรียกซ้ำ และสแตกแบบวนซ้ำ
- องค์ประกอบที่เชื่อมต่อกันและการเติมพื้นที่