สร้างรายการประชิดจากข้อมูลเข้า
สร้างกราฟตามรูปแบบที่การแข่งขันให้มา
สร้างรายการประชิดจากข้อมูลเข้า เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
กราฟคืออะไร
กราฟก็คือจุดต่าง ๆ ที่เรียกว่าโหนด ซึ่งเชื่อมกันด้วยเส้นที่เรียกว่าเส้นเชื่อม เมืองที่เชื่อมกันด้วยถนนคือกราฟที่คุณคุ้นเคยอยู่แล้ว 🗺️
โหนดและเส้นเชื่อม
แต่ละโหนดคือสิ่งหนึ่งสิ่งใด และแต่ละเส้นเชื่อมบอกว่าโหนดสองโหนดเชื่อมต่อกัน กราฟในการแข่งขันมักกำหนดหมายเลขโหนดตั้งแต่ 1 ถึง n
รายการเพื่อนบ้าน
โครงสร้างจัดเก็บที่นิยมใช้ในการแข่งขันคือรายการเพื่อนบ้าน: สำหรับแต่ละโหนด ให้เก็บรายการโหนดเพื่อนบ้านที่เชื่อมต่อโดยตรง
adj = [[] for _ in range(n + 1)]เหตุใดจึงไม่ใช้เมทริกซ์
เมทริกซ์ใช้หน่วยความจำ n ยกกำลังสอง ซึ่งเพิ่มขึ้นอย่างมากเมื่อ n มีค่ามาก ส่วนรายการเพื่อนบ้านจะเก็บเฉพาะเส้นเชื่อมที่มีอยู่จริง จึงรองรับกราฟขนาดใหญ่ได้ดีกว่า
อ่านบรรทัดแรก
อินพุตส่วนใหญ่เริ่มด้วยตัวเลขสองตัว: n โหนดและ m เส้นเชื่อม ให้อ่านสองค่านี้ก่อน เพื่อให้ทราบว่าจะมีเส้นเชื่อมที่ต้องอ่านกี่เส้น
n, m = map(int, input().split())หนึ่งเส้นเชื่อมต่อหนึ่งบรรทัด
m บรรทัดถัดไปแต่ละบรรทัดให้คู่ u v เส้นเชื่อมเพียงเส้นเดียวนั้นหมายความว่า u และ v เชื่อมต่อกันโดยตรง
u, v = map(int, input().split())ไม่มีทิศทางหมายถึงไปได้ทั้งสองทาง
สำหรับเส้นเชื่อมแบบไม่มีทิศทาง ให้เพิ่มการเชื่อมโยงทั้งสองทิศทาง คุณสามารถเดินจาก u ไป v และจาก v ไป u ได้
adj[u].append(v)
adj[v].append(u)มีทิศทางหมายถึงไปได้ทางเดียว
สำหรับเส้นเชื่อมแบบมีทิศทาง ให้เก็บเฉพาะการเชื่อมจาก u ไป v อ่านโจทย์อย่างละเอียดเพื่อดูว่ากราฟเป็นประเภทใด
adj[u].append(v)สร้างด้วยลูป
วนลูป m ครั้ง อ่านแต่ละคู่ แล้วเติมข้อมูลลงในรายการ เมื่อจบลูป รายการเพื่อนบ้านของคุณจะเก็บกราฟทั้งหมดไว้
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)ดัชนีเริ่มที่ 1 เทียบกับเริ่มที่ 0
หากโหนดเริ่มที่ 1 ให้กำหนดขนาดรายการเป็น n + 1 เพื่อให้ดัชนี n ใช้งานได้ การสับสนเรื่องการกำหนดดัชนีทำให้เกิดข้อผิดพลาดที่สังเกตได้ยาก
เยี่ยมชมเพื่อนบ้านของโหนด
เมื่อสร้างเสร็จแล้ว การสำรวจทำได้ง่าย เพียงวนดูรายการเพื่อนบ้านของโหนดเพื่อเข้าถึงเพื่อนบ้านทุกตัวในขั้นตอนเดียว
for nb in adj[u]:
print(nb)ตรวจสอบอย่างรวดเร็ว
คุณอ่านเส้นเชื่อมแบบไม่มีทิศทาง u v แล้วต้องเก็บข้อมูลใด
ทบทวน
ตอนนี้คุณสามารถสร้างกราฟเป็นรายการเพื่อนบ้านได้แล้ว: อ่าน n และ m วนดูเส้นเชื่อม และเพิ่มทั้งสองทิศทางเมื่อเป็นกราฟแบบไม่มีทิศทาง 🎉
คำถามที่พบบ่อย
บทเรียน “สร้างรายการประชิดจากข้อมูลเข้า” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “สร้างรายการประชิดจากข้อมูลเข้า” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “สร้างรายการประชิดจากข้อมูลเข้า”
สร้างกราฟตามรูปแบบที่การแข่งขันให้มา คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “สร้างรายการประชิดจากข้อมูลเข้า” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- สร้างรายการประชิดจากข้อมูลเข้า
- BFS สำหรับพาธสั้นที่สุดแบบไม่มีน้ำหนัก
- DFS การเรียกซ้ำ และสแตกแบบวนซ้ำ
- องค์ประกอบที่เชื่อมต่อกันและการเติมพื้นที่