Please enable JavaScript.
Coggle requires JavaScript to display documents.
หน่วยที่ 6 ต้นไม (Trees) (การแวะผ่านจุดในต้นไม้ (Tree Traversal) (Infix,…
หน่วยที่ 6 ต้นไม
(Trees)
บทนำ
กราฟต้นไม้
:recycle:
กราฟที่มีลักษณะเฉพาะคือมีโครงสร้างแบบลําดับชั้น
ตัวอย่าง
ต้นไม้แสดงความสัมพันธ์ในครอบครัว :silhouette:
ต้นไม้แสดงโครงสร้างขององค์กร :silhouettes:
นิยาม
นิยามที่ 6.1
กราฟแบบไม่มีทิศทางที่เชื่อมต่อกัน (connected undirected graph)
ซึ่งไม่มีวงจรแบบง่าย
วงจรแบบง่าย
เส้นเชื่อมหลายเส้นระหว่างคู่ของจุด
ลูป
นิยามที่ 6.2
ต้นไม้มีราก (Rooted tree) คือ ต้นไม้ที่มีการกําหนดจุดๆ หนึ่งเป็นรากและทุกๆ
เส้นเชื่อมพุ่งไปในทิศทางที่ออกจากราก
เลขระดับ
:forbidden:
ความยาวของทางเดินจากรากไปยังจุดนั้นๆ
รากจะอยู่ในระดับ (level) ที่ 0
จุดที่ต่ออยู่กับรากจะอยู่ในระดับที่ 1
จุดที่ต่ออยู่กับจุดในระดับ 1 จะอยู่ในระดับที่ 2
ความสูง
:explode:
ของต้นไม้จะมีค่าเท่ากับเลขระดับที่มีค่ามากที่สุดของจุดใน
ต้นไม้นั้น
ความสัมพันธ์ของจุดต่างๆ ในต้นไม้มีราก
:star:
ลูกหลาน (Descendants) ของจุด v คือ จุดอื่นๆ ที่มี v เป็นบรรพบุรุษ
ใบ (Leaf) คือ จุดใดๆ ในต้นไม้ที่ไม่มีลูก
จุดภายใน (Internal vertices) คือ จุดใดๆ ในต้นไม้ที่มีลูก
ต้นไม้ย่อย (Subtree) ที่มีจุด v เป็นราก คือ กราฟย่อยของต้นไม้ที่ประกอบด้วย
จุด v และลูกหลานทั้งหมดของจุด v
นิยามที่6.3
ต้นไม้มีรากจะเรียกว่าเป็น ต้นไม้แบบ m ภาค (m-ary tree) ถ้าทุกๆ จุด * ภายในมี ลูกไม่เกิน m และจะเรียกว่าเป็น ต้นไม้แบบเต็ม m ภาค (full m-ary tree) ถ้าทุกๆ จุด ภายในมีลูกเท่ากับ m เท่านั้น
การแวะผ่านจุดในต้นไม้ (Tree Traversal)
Infix, Prefix, and Postfix Notation
รูปแบบการเขียนนิพจน์ทางคณิตศาสตร์โดยทั่วไปจะอยู่ในรูปของ infix
notation ซึ่งมีวงเล็บประกอบ เช่น (a+b) × c
Infix form สามารถแสดงโดยใช้ต้นไม้มีรากหนึ่งต้น เรียกว่า “ต้นไม้นิพจน์
(Expression Tree)”
เนื่องจากการแสดงด้วย prefix notation และ postfix notation จะทําให้
เกิดความสับสนน้อยกว่าและสามารถที่จะประมวลผลได้ง่ายเพราะไม่ต้อง
สแกนกลับไปกลับมา เช่น
prefix form : × + abc
postfix form : ab + c ×
การแปลงจาก Infix form เป็น prefix และ postfix form
Infix ---> Prefix
Use preorder traversal
Infix ---> Postfix
Use postorder traversal
ตัวอย่าง
ต้นไม้มีรากแบบลําดับใช้เพื่อแสดง
ข้อมูลที่เก็บในคอมพิวเตอร์
การแสดงค่าชนิดต่างๆ เช่น สูตรทางคณิตศาสตร์ ดังนั้น เราจําเป็นที่จะต้องสามารถแวะแต่ละจุดในต้นไม้มีรากแบบลําดับได้ เพื่อเข้าถึง
ข้อมูลหรือประมวลผลสูตร
อัลกอริทึมการแวะผ่าน
จุดในต้นไม้มีรากแบบลําดับ
Preorder Traversal
ให้ T เป็นต้นไม้มีรากแบบลําดับที่มีราก คือ r
ถ้า T มีแค่ r จะได้ว่า r คือ postorder traversal ของ T
Inorder Traversal
ให้ T เป็นต้นไม้มีรากแบบลําดับที่มีราก คือ r
ถ้า T มีแค่ r จะได้ว่า r คือ inorder traversal ของ T
Postorder Traversal
ให้ T เป็นต้นไม้มีรากแบบลําดับที่มีราก คือ r
ถ้า T มีแค่ r จะได้ว่า r คือ preorder traversal ของ T
ต้นไม้แบบแผ่ (Spanning Trees)
นิยามที่ 6.7 ให้ G เป็นกราฟแบบง่าย ต้นไม้แบบแผ่ของ G คือ กราฟย่อยของ G ที่เป็นต้นไม้ ซึ่งประกอบด้วยทุกๆจุดของ G
กราฟแบบง่ายซึ่งเป็นกราฟแบบ connected ทุกๆ กราฟจะมีต้นไม้แบบแผ่
อัลกอริทึมสำหรับการสร้างต้นไม้แบบแผ่
การค้นตามความกว้าง (Breadth - First Search)
ตัวอย่างที่ จงหาต้นไม้แบบแผ่ของกราฟต่อไปนี้ โดยใช้อัลกอริทึมแบบ
Breadth-First Search
การค้นตามความลึก (Depth - First Search) หรือการย้อนรอย (Backtracking)
ตัวอย่างที่ จงหาต้นไม้แบบแผ่ของกราฟต่อไปนี้ โดยใช้อัลกอริทึมแบบ
Depth-First Search
ต้นไม้แบบแผ่ที่เล็กที่สุด (Minimum Spanning Trees)
สําหรับกราฟแบบมีน้ําหนัก การหาต้นไม้แบบแผ่จะพิจารณาจากผลบวกของน้ําหนักของเส้นเชื่อมที่มีค่าน้อยที่สุด
นิยามที่ 6.8
ต้นไม้แบบแผ่ที่เล็กที่สุดในกราฟแบบมีน้ําหนักที่เชื่อมต่อกัน คือ ต้นไม้แบบแผ่ที่มีผลรวมของน้ําหนักของเส้นเชื่อมที่น้อยที่สุด
อัลกอริทึมสําหรับต้นไม้แบบแผ่ที่เล็กที่สุด
ผลลัพธ์ทั้งสองแบบเท่ากัน
Prim's Algorithm
Prim's algorithm จะเลือกเส้นเชื่อมที่มีน้ําหนักน้อยที่สุดซึ่งเชื่อมต่อ
กับจุดที่อยู่ในต้นไม้แบบแผ่และไม่ทําให้เกิดวงจรแบบง่าย
ตัวอย่าง จงหาต้นไม้แบบแผ่ที่เล็กที่สุดของกราฟต่อไปนี้โดยใช้Prim’s
algorithm
คำตอบที่เล็กที่สุด = 24
Kruskal's Algorithm
Kruskal's algorithm จะพิจารณาเลือกเส้นเชื่อมที่มีน้ําหนักน้อยที่สุด
และไม่ทําให้เกิดวงจรแบบง่าย โดยไม่สนใจว่าจะเชื่อมต่ออยู่กับจุดในต้นไม้แบบ
แผ่หรือไม่
ตัวอย่าง จงหาต้นไม้แบบแผ่ที่เล็กที่สุดของกราฟต่อไปนี้โดยใช้
Kruskal’s algorithm
คำตอบที่น้อยที่สุดคือ 24
