ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 6.3"
Aoy (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย 'สังเกตว่าหลังจากการรัน DFSALL แล้วจะได้ อะเรย์ pre และ pos…') |
Aoy (คุย | มีส่วนร่วม) |
||
| แถว 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 ใด ๆ อยู่ในลำดับซ้ำกันนั่นเอง) |
รุ่นแก้ไขเมื่อ 07:30, 16 กันยายน 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 ใด ๆ อยู่ในลำดับซ้ำกันนั่นเอง)
