418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 2

แนวคิด เราจะทำการพิจารณา node ทีละ node สมมติให้กำลังพิจารณาที่ node a แล้วดูว่า node a นั้นมี node อะไรอยู่ใน list ของมันบ้าง ถ้ามี เช่นมี node b อยู่ให้ทำการ เพิ่ม node a ใน list ของ node b แทน และทำการบวกจำนวน node ใน list ของ node b ขึ้นอีกหนึ่ง เมื่อทำแบบนี้จนครบทุก node จะได้ว่าเวลาการทำงานจะเป็น $O(|V|)$ และสำหรับแต่ละ node จะทำการไล่ไปตาม list ของมัน ซึ่งจำนวนของ list ทั้งหมดใน directed graph จะมีเท่ากับจำนวน edge ในกราฟพอดี ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น $O(|V|+|E|)$

จากแนวคิดข้างต้น เขียนเป็น 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>