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

ข้อย่อย 1

แนวคิด สังเกตว่าถ้าเรารัน DFS เราก็จะได้ต้นไม้ที่ได้จากการสำรวจมาหนึ่งต้น ซึ่งจากคุณสมบัติของต้นไม้ จะไม่มี cycle แต่สำหรับข้อนี้กราฟของเราเป็น undirected graph ดังนั้นถ้ามี edge ที่อยู่ในกราฟ แต่ไม่อยู่ในต้นไม้ ก็แสดงว่า edge นั้นเชื่อมระหว่าง node ที่เคยสำรวจไปแล้ว ซึ่งจะได้ว่ามี cycle อยู่ในกราฟนั่นเอง

จากแนวคิดข้างต้น เราก็จะทำการรัน DFS แต่การรันนี้ เราจะแก้ไข code ของ DFS นิดหน่อย โดยในขณะที่มันทำการบอกว่า edge $\{u,v\}\,$ ไหนเป็น edge ในต้นไม้นั้น เราก็จะทำการลบ node $v\,$ ออกจาก list ของ node $u\,$ พร้อมทั้งลบ node $u\,$ ออกจาก list ของ node $v\,$ ด้วย หลังจากการรัน DFS และการกระทำดังกล่าวข้างต้นจบไปแล้ว เราก็สำรวจ node ทีละ node ในกราฟ ถ้า node ไหนยังมี node อื่นอยู่ใน list ของตน แสดงว่า edge ที่เชื่อมระหว่างสอง node นี้ไม่ใช่ edge ในต้นไม้ เราก็จะได้กราฟมี cycle ส่วนวิธีการพิมพ์ cycle ดังกล่าว เราก็ทำการพิมพ์ edge ที่เหลือนี้ก่อน จากนั้นย้อนกลับไปตาม parent ของจุดปลาย node หนึ่งจากสอง node ไปเรื่อย ๆ จนกระทั่ง parent ของ node หนึ่ง ๆ มีค่าเท่ากับ node ปลายข้างนึงของ edge ที่พิมพ์ไปครั้งแรก ก็จะได้ cycle ที่ต้องการ

เขียน pseudocode ตามแนวคิดข้างต้น ได้ดังนี้ <geshi lang="c"> DFS(u)

   explored[u]=1
   for i=1 to d[u] do
   {
       v = a[u][i]
       if explored[v] = 0
       {
            parent[v] = u
            a[u][i] = NIL // ลบ node v ออกจาก list ของ node u
            a[i][u] = NIL  // ลบ node u ออกจาก list ของ node v ด้วย เนื่องจาก edge ในกราฟไม่มีทิศทาง
            DFS(v)
       }
   }

</geshi>

อัลกอริทึม FindCycle จะทำการหา cycle ในกราฟ ถ้ามีจะทำการพิมพ์ cycle นั้นออกมา โดยการเรียก PrintCycle แต่ถ้าไม่มีจะ return 0 <geshi lang="c"> FindCycle

   flag = 0
   DFS(u)
   for each node u in V
   {
       for i= 1 to d[u]
       {
        if a[u][i] != NIL
           flag = 1 // บอกว่ามี cycle ในกราฟ
           PrintCycle(u,a[u][i])
       }
   }
   if flag != 1 
       return 0   

</geshi>

<geshi lang="c"> PrintCycle(u,v)

   print (u,v)
   while parent[v] != u
   {
       print (parent[v],v)
   }
   print(parent[v],v)

</geshi>

เวลาการทำงานของอัลกอริทึมจะได้ว่า algorithm DFS มีการแก้ไขแค่นิดหน่อย ซึ่งขั้นตอนการทำงานที่เพิ่มไป ใช้เวลาเป็น constant time ดังนั้นเวลาจึงเป็น $O(m+n)\,$ เหมือนเดิม ส่วนเวลาการทำงานของ algorithm FindCycle จะใช้เวลาเป็น เวลาของ DFS บวกกับเวลาที่แต่ละ node ทำการสำรวจ node ที่ติดกับมันว่ายังมี edge เหลือหรือไม่ ซึ่งจะได้ว่าการทำงานคล้าย ๆ กับ DFS จึงมีเวลาการทำงานเท่ากันคือ $O(m+n)\,$ ดังนั้นเวลาการทำงานของ FindCycle จึงเป็น $O(m+n)+O(m+n)=O(m+n)\,$ และเวลาการทำงานของ PrintCycle จะทำงานตามจำนวน node ที่อยู่ใน cycle ซึ่งมากที่สุดคือ $O(n)\,$ ดังนั้นเวลาการทำงานรวมจึงเป็น $O(m+n)\,$ ตามที่โจทย์ต้องการ

ข้อย่อย 2

อ.วัฒนา