Icpc-train-2012/graphs

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา

การค้นหาในกราฟ

โจทย์ตัวอย่างการค้นหาในกราฟ

DFS: รับกราฟที่มี n โหนด m เส้นเชื่อม มีหมายเลขตั้งแต่ 1 ถึง n จากนั้นพิมพ์โหนดในกราฟตามลำดับ DFS โดยเริ่มการค้นหาที่โหนด 1

BFS: รับกราฟที่มี n โหนด m เส้นเชื่อม มีหมายเลขตั้งแต่ 1 ถึง n จากนั้นพิมพ์โหนดในกราฟตามลำดับ BFS โดยเริ่มการค้นหาที่โหนด 1

Input:

  • บรรทัดแรกระบุจำนวนเต็มสองจำนวน n และ m (1 <= n <= 1000; 1 <= m <= 10,000)
  • จากนั้นอีก m บรรทัด ระบุเส้นเชื่อม m เส้น แต่ละบรรทัดระบุจำนวนเต็มสองจำนวน a และ b (1 <= a <= n; 1 <= b <= n) เพื่อระบุว่ามีเส้นเชื่อมระหว่างโหนด a และ b

Output:

พิมพ์ลำดับของโหนดที่ DFS (หรือ BFS) เข้าไปทำงาน