418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 2
ไปยังการนำทาง
ไปยังการค้นหา
แนวคิด เราจะทำการพิจารณา node ทีละ node สมมติให้กำลังพิจารณาที่ node a แล้วดูว่า node a นั้นมี node อะไรอยู่ใน list ของมันบ้าง ถ้ามี เช่นมี node b อยู่ให้ทำการ เพิ่ม node a ใน list ของ node b แทน และทำการบวกจำนวน node ใน list ของ node b ขึ้นอีกหนึ่ง เมื่อทำแบบนี้จนครบทุก node จะได้ว่าเวลาการทำงานจะเป็น และสำหรับแต่ละ node จะทำการไล่ไปตาม list ของมัน ซึ่งจำนวนของ list ทั้งหมดใน directed graph จะมีเท่ากับจำนวน edge ในกราฟพอดี ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น
จากแนวคิดข้างต้น เขียนเป็น pseudocode ได้ดังนี้
<geshi lang="c"> DFS(u)
Initialize d[u] = 0 for all node u in V for each node u in V { for i = 1 to d[u] do { v= a[u][i] d[v] = d[v] + 1 a[v][d[v]]= u // add u in list of v } }
</geshi>