Summary B4 Final
สรุปเรื่อง Tree
โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน เรียกว่า โหนดพี่น้อง(Siblings)โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ (Leave Node)เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนด เรียกว่ากิ่ง (Branch)
1.การท่องไปแบบพรีออร์เดอร์(Preorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่างๆในทรีด้วยวิธี NLR มีขั้นตอนดังนี้
(1)เยือนโหนดราก
(2)ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3)ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2.การท่องไปแบบอินออร์เดอร์(Inorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่างๆในทรีด้วยวิธี LNRมีขั้นตอนการเดินดังต่อไปนี้
(1)ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2)เยือนโหนดราก
(3)ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3.การท่องไปแบบโพสออร์เดอร์(Postorder Traversal)เป็นการไปเยือนโหนดต่างๆในทรีด้วยวิธี LRNมีขั้นตอนการเดินดังต่อไปนี้
(1)ท่องไปในทรีย่อยทางซ้ายแบบโพสออร์เดอร
(2)ท่องไปในทรีย่อยทางขวาแบบโพสออร์เดอร์
(3)เยือนโหนดราก
สรุปเรื่อง Graph
การท่องไปในกราฟ
1.การค้นหาแบบกว้าง(Breadth-first Search)
1.1การค้นหาแบบกว้าง ในกราฟไม่มีทิศทาง รายชื่อโหนดที่พบจากการค้นหาแบบกว้าง มีได้หลายรายการขึ้นกับลำดับการเรียงโหนดประชิด
1.2การค้นหาแบบกว้าง ในกราฟแบบมีทิศทาง การค้นหาโหนดในกราฟทำได้ง่ายขึ้นถ้าใช้คิวเก็บลำดับของโหนดประชิดที่ต้องเยี่ยมต่อไป และใช้ตารางเก็บค่าโหนดประชิดของโหนดทุกโหนดในกราฟ
2.การค้นหาแบบลึก(Depth-first Search)จะต่างจากการค้นหาแบบกว้างตรงที่จุดเริ่มต้นที่จะไปเยี่ยมโหนดในกราฟมีหลายจุด จึงต้องกำหนดจุดเริ่มต้นสำหรับเยี่ยมเป็นจุดแรก การค้นหาแบบลึกใช้หลักการคล้ายแบบลำดับทรี
กราฟมีน้ำหนัก หมายถึง กราฟที่ทุกเอดจ์ มีค่าน้ำหนักกำกับซึ่งค่าน้ำหนักอาจสื่อถึงระยะทาง เวลา ค่าใช้จ่าย เป็นต้นนิยมนำไปใช้แก้ปัญหาหลักๆ 2 ปัญหา คือ
1.การสร้างต้นไม้ทอดข้ามน้อยที่สุด(Minimum Spanning Trees:MST)
1.1เรียงลำดับเอดจ์ ตามน้ำหนัก
1.2สร้างป่าที่ประกอบด้วยต้นไม้ว่างที่มีแต่โหนดและไม่มีเส้นเชื่อม
1.3เลือกเอดจ์ที่มีน้ำหนักน้อยที่สุดและยังไม่เคยถูกเลือกเลยถ้ามีน้ำหนักซ้ำกันหลายค่าในสุ่มมา 1 เส้น
1.4พิจารณาเอดจ์ที่เลือก ถ้านำมาประกอบในต้นไม้ทอดข้ามน้อยที่สุดแล้วเกิด วงรอบให้ตัดทิ้ง นอกนั้นให้นำมาประกอบเป็นเอดจ์ในต้นไม้ทอดข้ามน้อยที่สุด
5.ตรวจสอบเอดจ์ที่ต้องอ่านในกราฟ ถ้ายังอ่านไม่หมดให้ไปทำข้อ 3
2.การหาเส้นทางที่สั้นที่สุด(Shortest path) Dijkstra's Algorithm
ข้อกำหนดคือให้เซต S เก็บโหนดที่ผ่านได้และมีระยะทางห่างจากจุดเริ่มต้นสั้นที่สุด
ให้ W แทนโหนด นอกเซต Sให้ D แทนระยะทาง(distance)ที่สั้นที่สุดจากโหนดต้นทางไปโหนดใดๆ ในกราฟ โดยวิถีนี้ประกอบด้วย
โหนดในเซตS ถ้าไม่มีวิถี ให้แทนด้วยค่าอินฟินีตี๊ (Infinity)
2.1เริ่มต้นให้เซต S มีเพียงโหนดเดียว คือโหนดที่เป็นจุดเริ่มต้น
2.2คำนวณหาระยะทางจาก โหนดที่เป็นจุดเริ่มต้น ไปยังโหนดโหนดในกราฟ โดยยอมให้ใช้โหนด ในเซต S เป็นทางผ่านได้ถ้ามีมากกว่า 1 ทางให้เลือกทางที่สั้นที่สุด นำไปใส่ใน D ของแต่ละโหนด
2.3เลือกโหนด W ที่ห่างจากโหนดเริ่มต้นน้อยที่สุดไปไว้ใน S
