Psl66/week04 graph2

หน้านี้เป็นส่วนหนึ่งของวิชา Problem solving lab ปีการศึกษา 2566

สัปดาห์นี้โจทย์จะเป็นเรื่องกราฟ จะมีการทดสอบ bipartite graphs และ topological ordering

ตัวอย่างโค้ด: ตัวอย่างโค้ด BFS, ตัวอย่าง adjacency list และ DFS

รายการโจทย์และหมายเหตุ

• box - หาเส้นทางในกราฟทั่วไป แต่พิจารณาให้ดีว่าจะสร้างกราฟแทนการขยับของกล่องได้อย่างไร
• mid592_maze - หาเส้นทางที่ซับซ้อนขึ้น จะจัดการเรื่องประตูอย่างไร?

• bipartite - ตรวจสอบ bipartiteness
• mid62_ttt - อาจจะต้องลองหลายแบบ

• topo - topological ordering
• uva10305_orderingtasks - topological ordering

• twoteams - ทำตรง ๆ ไล่ไปเรื่อย ๆ อาจจะไม่ทัน จะทำอย่างไรให้เร็วขึ้น (มีวิธีอะไรบ้างที่ช่วยลดจำนวนการทดสอบ)

Optional

• mid61_dig - หาเส้นทางทั่วไป
• mid64_redblackbridges - จัดการกราฟให้ดี
• mid64_shipmentcost - กราฟไม่มีทิศทาง
• stardrawing - กราฟมีรูปแบบอย่างใดได้บ้าง