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

สังเกตว่าเมื่อเราพิจารณา edge $(a,b)\,$ ใด ๆ การที่เราจะหาว่า edge ดังกล่าวอยู่ใน cycle หรือไม่ ก็มีสองวิธีการ คือเริ่มทำการ DFS จาก node $a\,$ หรือไม่ก็ node $b\,$ แต่การเริ่มจาก node $a\,$ อาจได้ cycle ก็จริง แต่ cycle นั้นอาจไม่มี edge $(a,b)\,$ อยู่ก็ได้ ดังนั้นเราควรเริ่มทำการหา DFS จาก node $b\,$ ก่อน แล้วถ้ามันมี edge ย้อนกลับมาหา node $b\,$ ก็จะได้ว่ากราฟมี cycle ที่มี edge $(a,b)\,$ อยู่ด้วยนั่นเอง

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

<geshi lang="c"> DFS(b)

   flag = 0 // ให้ flag เป็นตัวแปรที่บอกว่ากราฟมี cycle ที่มี edge (a,b) อยู่หรือไม่
       explored[b]=1
   for each edge (b,v) in E // สำหรับแต่ละ edge (b,v) ที่กำลังพิจารณา ในที่นี้คือมี edge ชี้จาก b ไป v
   {    
       if b = a and v = b // ถ้า node ต้นทางนั้นเป็น a และ node ปลายทางเป็น b จะได้ว่า edge ที่กำลังพิจารณาคือ edge ที่โจทย์กำหนดนั่นเอง
              {
        flag = 1 
        FindCycle(b,v)
       } 
       if explored[v] = 0
       {
            parent[v] = b
            DFS(v)
       }
   }
   if flag != 1
       return 0

</geshi>

อัลกอริทึมการพิมพ์ cycle นี้จะทำงานคล้าย ๆ กับการพิมพ์ ของ undirected graph ข้อย่อยหนึ่ง แต่เนื่องจากทิศทางมีผล ดังนั้นเราจึงจะทำการสำรวจ node ที่อยู่ใน cycle ในอัลกอริทึม FindCycle แล้วเก็บใส่อะเรย์ C แล้วค่อยพิมพ์อะเรย์นั้นออกมาอีกทีในอัลกอริทึม PrintCycle <geshi lang="c"> FindCycle(u,v)

   j = n -2
   C[n] = v
   C[n-1] = u
   while parent[u] != v
   {
       C[j] = parent[u]
       j = j -1
       u = parent[u]
   }
   C[j] = u
   PrintCycle(C,j)

</geshi>

<geshi lang="c"> PrintCycle(C,j)

   for i = j to n do
       print (C[i],C[i+1])

</geshi>

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