อ่านบทความนี้ใน Facebook
“การจัดเก็บ file และ folder, สารบัญของหนังสือ, HTML, …”
เราเชื่อว่าทุคนน่าจะคุ้นเคยกับ structure พวกนี้ดีถึงความเป็น “hierarchical structure” (การมีลำดับชั้น) ของวิธีการจัดเก็บหรือเรียบเรียงข้อมูล
วิธีการเก็บข้อมูลนี้ก็คือสิ่งที่เรานิยมเรียกมันว่า “tree data structure” นั่นเอง …แต่แน่นอนจะเห็นว่า tree นั้น เราสามารถวาดมันออกมาได้ด้วย “วงกลม และ ลูกศร” (vertex and edge) โพสนี้เราเลยอยากชวนทุกคนมาทำความเข้าใจ “tree ในมุมมองของ graph theory กัน”
“Tree is a connected acyclic undirected graph.”
นี่คือนิยามของ tree ใน graph theory แต่หลายคนที่อ่านอาจจะสงสัยว่า what the heck is “connected acyclic undirected graph!?” …เพื่อให้เข้าใจ เรามาพยายามทำความเข้าใจไปทีละคำศัพท์ดีกว่าครับ
- “connected” หมายความว่าในระหว่าง vertex สองตัวใด ๆ ก็ตาม จะต้องมีเส้นทางเดินจาก A ไป B เสมอ ๆ
- “acyclic” หรือ “ไม่มี cycle” หมายความว่าไม่มี path ที่เดินกลับมาที่ vertex เดิมได้ (ตัวอย่าง graph ที่มี cycle เช่นเราสามารถเดิน A → B → C → A)
- “undirected” เป็น graph ที่ edge ไม่มีทิศทาง เราสามารถเดินไปทางไหนก็ได้
สุดท้ายภาพที่ออกมาก็คือ graph ในรูปปกด้านขวาเลย
แต่หลายคนอาจจะสงสัยว่า “แต่สารบัญมันมีลำดับขั้นหนิ? เรารู้ว่าหัวข้อใหญ่คืออะไร และในนั้นมีหัวข้อย่อยอะไรบ้าง” แต่จาก graph ตัวอย่าง “เราไม่รู้เลยว่าหัวข้อใหญ่คืออะไร?” หรือ “เราจะเริ่มต้นที่ vertex ไหน?”
ใช่ครับ และวิธีการแก้ปัญหาคือการ “กำหนด vertex ให้ vertex หนึ่งเป็น root” (เราเรียก connected acyclic undirected graph ที่มีการกำหนด root vertex ว่า “rooted tree”)
ความน่าสนใจก็คือว่า เมื่อเรากำหนด root มันทำให้เกิด concept หลาย ๆ อย่างตามมา เช่น “vertex นี้อยู่ห่างจาก root เท่าไหร่?” หรือ “vertex ไหนเป็น parent vertex ไหนบ้างที่เป็น child” …
โพสหน้าจะมาเล่าเรื่องนี้แบบละเอียดอีกทีครับ
