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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(หน้าที่ถูกสร้างด้วย 'สังเกตว่าหลังจากการรัน DFSALL แล้วจะได้ อะเรย์ pre และ pos…')
 
 
(ไม่แสดง 3 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน)
แถว 1: แถว 1:
สังเกตว่าหลังจากการรัน DFSALL แล้วจะได้ อะเรย์ pre และ post มา ซึ่งอะเรย์ pre จะบอกถึงเวลาที่ node นั้น ๆ เริ่มต้นถูกสำรวจ ส่วนอะเรย์ post จะบอกถึงเวลาที่ node นั้น ๆ สำรวจเสร็จ ดังนั้นเราจะได้ว่า node <math> u, v \, </math> สอง node ใด ๆ ถ้า pre ของ u มากกว่า pre ของ v แสดงว่า node u ถูกสำรวจก่อน node v (มิเช่นนั้นก็กลับกัน) ส่วนถ้า post ของ u มากกว่า post ของ v ก็จะได้ว่า การสำรวจ u เสร็จทีหลังการสำรวจ v นอกจากนี้การสังเกตว่า topological ordering คือการนำ node ในกราฟมาเรียงลำดับจากซ้ายไปขวา แล้ว edge ทุก edge ในกราฟจะชี้จากซ้ายไปขวา พิจารณา edge ที่ชี้จาก u ไป v ใน DAG ใด ๆ จะได้ว่า post ของ u ต้องมากกว่า post ของ v เสมอ (ความจริงจากข้อย่อย 6.1) ดังนั้น ถ้าเราทำการหา DFSALL แล้วทำการ order node จาก node ที่มีค่า post มากไปน้อย เราก็จะได้ topological ordering ตามที่เราต้องการ
+
สังเกตว่าหลังจากการรัน DFSALL แล้วจะได้ อะเรย์ pre และ post มา ซึ่งอะเรย์ pre จะบอกถึงเวลาที่ node นั้น ๆ เริ่มต้นถูกสำรวจ ส่วนอะเรย์ post จะบอกถึงเวลาที่ node นั้น ๆ สำรวจเสร็จ ดังนั้นเราจะได้ว่า node <math> u, v \, </math> สอง node ใด ๆ ถ้า pre ของ u มากกว่า pre ของ v แสดงว่า node u ถูกสำรวจก่อน node v (มิเช่นนั้นก็กลับกัน) ส่วนถ้า post ของ u มากกว่า post ของ v ก็จะได้ว่า การสำรวจ u เสร็จทีหลังการสำรวจ v นอกจากนี้การสังเกตว่า topological ordering คือการนำ node ในกราฟมาเรียงลำดับจากซ้ายไปขวา แล้ว edge ทุก edge ในกราฟจะชี้จากซ้ายไปขวา พิจารณา edge ที่ชี้จาก u ไป v ใน DAG ใด ๆ จะได้ว่า post ของ u ต้องมากกว่า post ของ v เสมอ (ความจริงจากข้อย่อย 6.1) ดังนั้น ถ้าเราทำการหา DFSALL แล้วทำการ order node จาก node ที่มีค่า post มากไปน้อย เราก็จะได้ topological ordering ตามที่เราต้องการ (มีข้อสังเกตอีกอย่างคือ เนื่องจากค่าในอะเรย์ post เป็นค่าของเวลา และเมื่อทำการบันทึกค่าของเวลาที่ node ใด ๆ ถูกสำรวจเสร็จแล้ว เราจะทำการเพิ่มค่าของตัวแปร clock ขึ้นอีกหนึ่ง จึงทำให้ค่าของอะเรย์ post เหล่านี้ไม่ซ้ำกันในแต่ละช่อง ดังนั้นถ้าเราเรียงตามค่า post ก็จะไม่มี node สอง node ใด ๆ อยู่ในลำดับซ้ำกันนั่นเอง)
 +
 
 +
จากแนวคิดข้างต้น นำมาเขียนเป็น pseudocode ได้ดังนี้
 +
 
 +
ในส่วนของอัลกอริทึม DFSALL จะทำเหมือนเดิม แต่ DFS จะทำการเพิ่มอะเรย์ order ให้เก็บลำดับการเรียงที่เราต้องการ โดยจะทำการใส่ค่าให้อะเรย์นี้เมื่อ node นั้นถูกสำรวจเรียบร้อยแล้ว และการใส่ค่าจะใส่จากหลังไปหน้า
 +
 
 +
<geshi lang="c">
 +
DFS(u)
 +
{
 +
    j = n
 +
    pre[u] = clock
 +
    clock = clock + 1
 +
    explored[u] = 1
 +
   
 +
    for i = 1 to d[u] do
 +
    {
 +
        v = a[u][i]
 +
        if explored[v] = 0 then
 +
        {
 +
            parent[v] = u
 +
            DFS(v)
 +
        }
 +
    }
 +
 
 +
    post[u] = clock
 +
    order[j] = u // อะเรย์ order เก็บลำดับของการเรียงที่เราต้องการ
 +
        j = j-1 //การใส่ลำดับของ node นี้จะใส่จากหลังมาหน้า
 +
    clock = clock + 1
 +
}
 +
</geshi>
 +
 
 +
 
 +
<geshi lang="c">
 +
DFSALL()
 +
{
 +
    for u = 1 to n do
 +
          if explored[u] = 0 then
 +
          {
 +
              parent[u] = 0
 +
              DFS(u)
 +
          }
 +
}
 +
</geshi>
 +
 
 +
<geshi lang="c">
 +
Topological_DFSALL()
 +
    DFSALL()
 +
    for i = 1 to n do
 +
        print order[i]
 +
</geshi>

รุ่นแก้ไขปัจจุบันเมื่อ 16:14, 20 กันยายน 2552

สังเกตว่าหลังจากการรัน DFSALL แล้วจะได้ อะเรย์ pre และ post มา ซึ่งอะเรย์ pre จะบอกถึงเวลาที่ node นั้น ๆ เริ่มต้นถูกสำรวจ ส่วนอะเรย์ post จะบอกถึงเวลาที่ node นั้น ๆ สำรวจเสร็จ ดังนั้นเราจะได้ว่า node สอง node ใด ๆ ถ้า pre ของ u มากกว่า pre ของ v แสดงว่า node u ถูกสำรวจก่อน node v (มิเช่นนั้นก็กลับกัน) ส่วนถ้า post ของ u มากกว่า post ของ v ก็จะได้ว่า การสำรวจ u เสร็จทีหลังการสำรวจ v นอกจากนี้การสังเกตว่า topological ordering คือการนำ node ในกราฟมาเรียงลำดับจากซ้ายไปขวา แล้ว edge ทุก edge ในกราฟจะชี้จากซ้ายไปขวา พิจารณา edge ที่ชี้จาก u ไป v ใน DAG ใด ๆ จะได้ว่า post ของ u ต้องมากกว่า post ของ v เสมอ (ความจริงจากข้อย่อย 6.1) ดังนั้น ถ้าเราทำการหา DFSALL แล้วทำการ order node จาก node ที่มีค่า post มากไปน้อย เราก็จะได้ topological ordering ตามที่เราต้องการ (มีข้อสังเกตอีกอย่างคือ เนื่องจากค่าในอะเรย์ post เป็นค่าของเวลา และเมื่อทำการบันทึกค่าของเวลาที่ node ใด ๆ ถูกสำรวจเสร็จแล้ว เราจะทำการเพิ่มค่าของตัวแปร clock ขึ้นอีกหนึ่ง จึงทำให้ค่าของอะเรย์ post เหล่านี้ไม่ซ้ำกันในแต่ละช่อง ดังนั้นถ้าเราเรียงตามค่า post ก็จะไม่มี node สอง node ใด ๆ อยู่ในลำดับซ้ำกันนั่นเอง)

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

ในส่วนของอัลกอริทึม DFSALL จะทำเหมือนเดิม แต่ DFS จะทำการเพิ่มอะเรย์ order ให้เก็บลำดับการเรียงที่เราต้องการ โดยจะทำการใส่ค่าให้อะเรย์นี้เมื่อ node นั้นถูกสำรวจเรียบร้อยแล้ว และการใส่ค่าจะใส่จากหลังไปหน้า

<geshi lang="c"> DFS(u) {

   j = n
   pre[u] = clock
   clock = clock + 1
   explored[u] = 1
   
   for i = 1 to d[u] do
   {
       v = a[u][i]
       if explored[v] = 0 then
       {
           parent[v] = u
           DFS(v)
       }
   }
   post[u] = clock
   order[j] = u // อะเรย์ order เก็บลำดับของการเรียงที่เราต้องการ
       j = j-1 //การใส่ลำดับของ node นี้จะใส่จากหลังมาหน้า
   clock = clock + 1

} </geshi>


<geshi lang="c"> DFSALL() {

    for u = 1 to n do
         if explored[u] = 0 then
         {
              parent[u] = 0
              DFS(u)
         }

} </geshi>

<geshi lang="c"> Topological_DFSALL()

   DFSALL()
   for i = 1 to n do
       print order[i]

</geshi>