topological sort of DAG

พี่ dax

topological sort of DAG คือการเรียงลำดับ node ใน Directed Acyclic Graph โดยสมาชิกตัวที่ x จะต้องถูกปริ้นก่อน y ถ้าในกราฟ x -> y

เช่นจากกราฟ

DAG

เราจะได้ว่าในกราฟกลุ่มแรก สามารถเรียงได้เป็น 0 1 2 5 3 4 และในกราฟกลุ่มที่สองเรียงได้เป็น 7 6

โอเค มาลองทำดูกัน

ในกลุ่มกราฟ ถ้าเรา dfs ไปเรื่อยๆ จะได้ว่า

• function ของ Edge ตัวสุดท้ายที่ทำงานเสร็จ จะเป็น leaf เสมอ
• ลำดับการทำงานเสร็จของ function ตัวต่อมาจะเป็น parent node ของตัวก่อนหน้า

เช่นจากกราฟในกลุ่มสีแดง

ถ้าเรา print edge ของ function ที่ทำงานเสร็จ ด้วย code ตามนี้

ได้ผลลัพธ์คือ 4 3 5 2 1 0 ซึ่งเป็นการ reverse ของ topological sort นั่นเอง

โดยเราจะเก็บใน vector แทนการ print แล้วค่อยมา print แบบ reverse ด้วย code ดังรูป

โอเค ทีนี้ปัญหาคือ เราต้องปริ้นค่าของกราฟทุกๆกลุ่ม … การวนทุกๆกลุ่มของกราฟเราจะให้ loop dfs เริ่มจากทุกๆ Edge ในกราฟที่ยังไม่เคยผ่านนั่นเอง ตาม code ด้านล่าง

โอเค มาประกอบ code ทั้งหมดกัน จะได้ code ตามนี้