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

แนวคิด เนื่องจากกราฟที่ให้มาเป็นกราฟแบบมีทิศทาง ดังนั้นเมื่อเรารัน DFS แล้วเราก็จะได้ edge แบบต่าง ๆ มา คือเป็น tree edge, back edge, forward edge และ cross edge ซึ่งตามนิยามเราจะได้ว่า back edge คือ edge ที่พุ่งออกจาก vertex ไปหาบรรพบุรุษของมัน นั่นก็คือ พุ่งกลับไปหา vertex ที่เคยสำรวจไปแล้วนั่นเอง ดังนั้นถ้ากราฟมี back edge เราก็สามารถสรุปได้ว่ากราฟมี cycle นั่นเอง นั่นแสดงว่าโจทย์ข้อนี้เราก็ทำการรัน DFS แล้วหาว่ามี back edge หรือไม่ ถ้ามีก็ทำการพิมพ์ cycle นั้นออกมา

นำแนวคิดข้างต้นไปเขียนเป็น pseudocode ได้ดังนี้

อัลกอริทึม CheckCycle จะทำการตรวจสอบว่ามี cycle อยู่ในกราฟหรือไม่ ถ้ามีจะทำการพิมพ์ออกมา โดยเรียก FindCycle และ PrintCycle ที่มีการทำงานเหมือนกับข้อ 3.2 <geshi lang="c"> CheckCycle()

   DFS(u)
   flag = 0
   for each u in V
   {
    for each edge (u,v) in E
    {
     if pre[v] < pre[u]< post[u] < post[v] then
     {
        flag = 1
        FindCycle(u,v)
     } 
    }
   }

</geshi>

เวลาการทำงานของ CheckCycle จะเป็นเวลาของ DFS บวกกับเวลาที่แต่ละ node ทำการตรวจสอบ edge ที่ติดกับมันว่าเป็น back edge หรือไม่ บวกกับเวลาของ FindCycle บวกกับเวลาของ PrintCycle ซึ่งเหมือนกับการวิเคราะห์ในข้อ 3.2 ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น $O(|V|+|E|)$