ผลต่างระหว่างรุ่นของ "Icpc-train-2012/graphs"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 1: | แถว 1: | ||
| − | == โจทย์ตัวอย่างการค้นหาในกราฟ == | + | == การค้นหาในกราฟ == |
| + | |||
| + | === โจทย์ตัวอย่างการค้นหาในกราฟ === | ||
'''DFS:''' รับกราฟที่มี n โหนด m เส้นเชื่อม มีหมายเลขตั้งแต่ 1 ถึง n จากนั้นพิมพ์โหนดในกราฟตามลำดับ DFS โดยเริ่มการค้นหาที่โหนด 1 | '''DFS:''' รับกราฟที่มี n โหนด m เส้นเชื่อม มีหมายเลขตั้งแต่ 1 ถึง n จากนั้นพิมพ์โหนดในกราฟตามลำดับ DFS โดยเริ่มการค้นหาที่โหนด 1 | ||
| แถว 8: | แถว 10: | ||
* บรรทัดแรกระบุจำนวนเต็มสองจำนวน n และ m (1 <= n <= 1000; 1 <= m <= 10,000) | * บรรทัดแรกระบุจำนวนเต็มสองจำนวน n และ m (1 <= n <= 1000; 1 <= m <= 10,000) | ||
| − | * จากนั้นอีก m บรรทัด | + | * จากนั้นอีก m บรรทัด ระบุเส้นเชื่อม m เส้น แต่ละบรรทัดระบุจำนวนเต็มสองจำนวน a และ b (1 <= a <= n; 1 <= b <= n) เพื่อระบุว่ามีเส้นเชื่อมระหว่างโหนด a และ b |
| + | |||
| + | '''Output:''' | ||
| + | |||
| + | พิมพ์ลำดับของโหนดที่ DFS (หรือ BFS) เข้าไปทำงาน | ||
รุ่นแก้ไขเมื่อ 18:06, 7 กรกฎาคม 2555
การค้นหาในกราฟ
โจทย์ตัวอย่างการค้นหาในกราฟ
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) เข้าไปทำงาน
