บทนำ
ในการเขียนโปรแกรม Data Type (ชนิดข้อมูล) ระบุลักษณะและรูปแบบของข้อมูลที่จะใช้งาน ส่วน Data Structure (โครงสร้างข้อมูล) คือวิธีจัดเก็บและจัดระเบียบข้อมูล ข้อมูลแบ่งหลักได้ 2 ประเภทคือ Linear (เส้นตรง) และ Non-Linear (ไม่เส้นตรง) สำหรับข้อมูล Non-Linear โครงสร้างที่นิยมใช้คือ Graph (กราฟ) และ Tree (ต้นไม้) ทั้งคู่ประกอบด้วย Nodes (โหนด) และ Edges (ขอบ/เส้นเชื่อม) แต่มีความแตกต่างกันสำคัญ
ตารางเปรียบเทียบ Graph และ Tree
| ลำดับ | หัวข้อ | Graph | Tree |
|---|---|---|---|
| 1 | นิยาม | การแสดงข้อมูล Non-Linear โดยโหนดแทนข้อมูล และ Edge แทนความสัมพันธ์ | การแสดงข้อมูลแบบลำดับชั้น (Hierarchy) โหนดบนเป็น Parent โหนดล่างเป็น Child |
| 2 | การนำไปใช้ (Implementation) | โหนดอาจเชื่อมต่อกัน หรือไม่เชื่อมต่อก็ได้ อาจมี Self-loop | ทุกโหนด (ยกเว้น Root) ต้องมี Parent อย่างน้อย 1 ตัว ไม่มี Loop หรือ Self-loop |
| 3 | การค้นหาข้อมูล | ยาก เนื่องจากอาจมี Self-loop ต้องติดตามเส้นทางให้ถูกต้อง | ง่าย เนื่องจากเป็นลำดับชั้น สามารถ Traversal (DFS, BFS) ได้อย่างมีระบบ |
| 4 | ความสัมพันธ์ Parent-Child | ไม่มี เพราะไม่ได้แสดงแบบลำดับชั้น | มีชัดเจน ทุกโหนด (ยกเว้น Root) มี Parent อย่างน้อย 1 ตัว |
| 5 | ความสัมพันธ์ย้อนกลับ | Graph ทุกตัวไม่ใช่ Tree | Tree ทุกตัวเป็น Graph (Tree เป็นกรณีพิเศษของ Graph ที่ไม่มี Cycle) |
| 6 | การประยุกต์ใช้หลัก | Graph Coloring, Job Scheduling, Shortest Path, Network Flow | Sorting (Heap Sort), Traversal, Expression Tree, Decision Tree, File System |
ความแตกต่างสำคัญเพิ่มเติม
- Cycle: Graph อาจมี Cycle (วงจร) ได้ Tree ห้ามมี Cycle
- Edges: Graph สามารถมี Edge ได้ไม่จำกัด Tree ที่มี n โหนด จะมี Edge อย่างแน่นอน n-1 เส้น
- Root: Graph ไม่มี Root Tree มี Root อย่างแน่นอน 1 ตัว
สรุป
Tree เป็นกรณีพิเศษของ Graph ที่มีโครงสร้างเข้มงวดกว่า (Connected, Acyclic, Hierarchical) เลือกใช้ Graph เมื่อข้อมูลมีความสัมพันธ์ซับซ้อนหลายทิศทาง เลือกใช้ Tree เมื่อข้อมูลมีโครงสร้างลำดับชั้นชัดเจน
