DTS 09-14/09/2009

Graph

กราฟ (Graph) เป็นโครงสร้างข้อมูล
แบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็น
โครงสร้างข้อมูลที่มีการนำไปใช้ในงาน
ที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน
เช่น การวางข่าย งานคอมพิวเตอร์ การ
วิเคราะห์เส้นทางวิกฤติ และปัญหาเส้นทาง
ที่สั้นที่สุด
นิยามของกราฟ
กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น
ที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
(1) โหนด (Nodes) หรือ เวอร์เทกซ์(Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)
กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนด
ถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่า
กราฟแบบไม่มีทิศทาง (Undirected Graphs)
และถ้ากราฟนั้นมีเอ็จที่มีลำดับ
ความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟ
นั้นว่า กราฟแบบมีทิศทาง(Directed Graphs)
บางครั้งเรียกว่า ไดกราฟ (Digraph)
ถ้าต้องการอ้างถึงเอ็จแต่ละเส้นสามารถเขียนชื่อเอ็จกำกับไว้ก็ได้
การแทนกราฟในหน่วยความจำ
ในการปฏิบัติการกับโครงสร้างกราฟ สิ่งที่
ต้องการจัดเก็บ จากกราฟโดยทั่วไปก็คือ เอ็จ ซึ่ง
เป็นเส้นเชื่อมระหว่างโหนดสองโหนด มีวิธีการ
จัดเก็บหลายวิธี วิธีที่ง่ายและตรงไปตรงมา
ที่สุดคือ การเก็บเอ็จในแถวลำดับ 2 มิติ
การท่องไปในกราฟ
การท่องไปในกราฟ (graph traversal) คือ
กระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการ
ทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับ
การท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียว
แต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้น
เพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำ
เครื่องหมายบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้ว
เพื่อไม่ให้เข้าไปเยือนอีก สำหรับเทคนิคการท่องไป
ในกราฟมี 2 แบบดังนี้
1. การท่องแบบกว้าง (Breadth First Traversal)
วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนด
อื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุก
โหนดในกราฟ
2. การท่องแบบลึก (Depth First Traversal)
การทำงานคล้ายกับการท่องทีละระดับของทรี โดย
กำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตาม
แนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น
ย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่ง
สามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือน
โหนดอื่น ๆ ต่อไปจนครบทุกโหนด

DTS 08-25/08/2009

Tree

ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์
ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับ
ชั้น (Hierarchical Relationship)
แต่ละโหนดจะมีความสัมพันธ์กับโหนดใน
ระดับที่ต่ำลงมา หนึ่งระดับได้หลาย ๆ โหนด
เรียกโหนดดังกล่าวว่า โหนดแม่ (Parent or
Mother Node)
โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับ
เรียกว่า โหนดลูก (Child or Son Node)
โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่
เรียกว่า โหนดราก (Root Node)
โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน
เรียกว่า โหนดพี่น้อง (Siblings)
โหนดที่ไม่มีโหนดลูก เรียกว่า
โหนดใบ (Leave Node)
เส้นเชื่อมแสดงความสัมพันธ์ระหว่าง
โหนดสองโหนดเรียกว่า กิ่ง (Branch)
นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มี
วงจรปิด (loop) ในโครงสร้าง โหนดสองโหนด
ใด ๆ ในทรีต้องมีทางติดต่อกัน
ทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่ง
ทั้งหมด N-1 เส้น
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ
ทรีประกอบด้วยสมาชิกที่เรียกว่า
โหนด โดยที่ ถ้าว่าง ไม่มีโหนดใด ๆ
เรียกว่านัลทรี (Null Tree) และถ้ามีโหนด
หนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็น
ทรีย่อย (Sub Tree)
T1, T2, T3,…,Tk โดยที่ k>=0
และทรีย่อย
ต้องมีคุณสมบัติเป็นทรี
นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์ (Forest)
หมายถึง กลุ่มของทรีที่เกิดจากการ
เอาโหนดรากของทรีออก
หรือ เซตของทรีที่แยกจากกัน(Disjoint Trees)
2. ทรีที่มีแบบแผน (Ordered Tree)
หมายถึง ทรีที่โหนดต่าง ๆ ในทรีนั้นมี
ความสัมพันธ์ที่แน่นอน เช่น ไปทางขวา
ไปทางซ้าย
3. ทรีคล้าย (Similar Tree)
คือทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มี
รูปร่างของทรีเหมือนกัน โดยไม่คำนึงถึง
ข้อมูลที่อยู่ในแต่ละโหนด
4. ทรีเหมือน (Equivalent Tree)
คือทรีที่เหมือนกันโดยสมบูรณ์ โดยต้องเป็นทรีที่
คล้ายกันและแต่ละโหนดในตำแหน่ง
เดียวกันมีข้อมูลเหมือนกัน
5. กำลัง (Degree)
หมายถึงจำนวนทรีย่อยของโหนด นั้น ๆ
ในรูปโหนด “B” มีกำลังเป็น 1 เพราะ
มีทรีย่อย คือ {“D”}
ส่วนโหนด “C” มีค่ากำลังเป็นสอง เพราะ
มีทรีย่อย คือ {“E”, “G”, “H”, “I”} และ {“F”}
6. ระดับของโหนด (Level of Node)
คือระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนด
ราก เมื่อกำหนดให้ โหนดรากของทรีนั้นอยู่ระดับ 1
และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือ ยาวเท่ากับ 1
หน่วย ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุด
จากโหนดรากไปยังโหนดใด ๆ บวกด้วย 1
และจำนวนเส้นทางตามแนวดิ่งของโหนดใด ๆ ซึ่งห่าง
จากโหนดราก เรียกว่า ความสูง (Height)
หรือความลึก (Depth)
การแทนที่ทรีในหน่วยความจำหลัก
การแทนที่โครงสร้างข้อมูลแบบทรีในความจำหลัก
จะมีพอยเตอร์เชื่อมโยงจากโหนดแม่ไปยังโหนดลูก แต่ละ
โหนดต้องมีลิงค์ฟิลด์เพื่อเก็บที่อยู่ของโหนดลูกต่าง ๆ นั่นคือ
จำนวน ลิงค์ฟิลด์ของแต่ละโหนดขึ้นอยู่กับจำนวนของ
โหนดลูก
1. โหนดแต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูก
ทุกโหนด การแทนที่ทรีด้วยวิธีนี้ จะให้จำนวนฟิลด์ในแต่ละ
โหนดเท่ากันโดยกำหนดให้มีขนาดเท่ากับจำนวนโหนดลูก
ของโหนดที่มีลูกมากที่สุด โหนดใดไม่มีโหลดลูกก็ให้ค่า
พอยเตอร์ในลิงค์ฟิลด์นั้นมีค่าเป็น Null
และให้ลิงค์ฟิลด์แรกเก็บค่าพอยเตอร์ชี้ไปยังโหนด ลูกลำดับ
ที่หนึ่ง ลิงค์ฟิลด์ที่สองเก็บค่าพอยเตอร์ชี้ไปยังโหนดลูก
ลำดับที่สอง และลิงค์ฟิลด์อื่นเก็บค่าพอยเตอร์ของโหนดลูก
ลำดับ ถัดไปเรื่อย ๆ
2. แทนทรีด้วยไบนารีทรี
เป็นวิธีแก้ปัญหาเพื่อลดการ สิ้นเปลืองเนื้อที่ในหน่วยความจำก็คือ
กำหนดลิงค์ฟิลด์ให้มีจำนวนน้อยที่สุดเท่าที่จำเป็นเท่านั้น
โดยกำหนดให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์สองลิงค์ฟิลด์
-ลิงค์ฟิลด์แรกเก็บที่อยู่ของโหนดลูกคนโต
-ลิงค์ฟิลด์ที่สองเก็บที่อยู่ของโหนดพี่น้องที่เป็นโหนดถัดไป
โหนดใดไม่มีโหนดลูกหรือไม่มีโหนดพี่น้องให้ค่าพอยน์เตอร์ใน
ลิงค์ฟิลด์มีค่าเป็น Null
การแปลงทรีทั่วไปให้เป็นไบนารีทรี
ขั้นตอนการแปลงทรีทั่วๆ ไปให้เป็น
ไบนารีทรี มีลำดับขั้นตอนการแปลง ดังต่อไปนี้
1. ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบ
ความสัมพันธ์ ระหว่างโหนดแม่และโหนดลูกอื่น ๆ
2. ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3. จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
1. การท่องไปแบบพรีออร์เดอร์
(Preorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี
NLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2.การท่องไปแบบอินออร์เดอร์
(Inorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธี LNR
มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3. การท่องไปแบบโพสออร์เดอร์
(Postorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
(3) เยือนโหนดราก
ไบนารีเซิร์ชทรี
ไบนารีเซิร์ชทรี (Binary Search Tree)
เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนด
ในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุก
โหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่า
หรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวา
และในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกัน

DTS 07-11/08/2009

Queue

คิว (Queue) เป็นโครงสร้างข้อมูลแบบเชิงเส้นหรือ
ลิเนียร์ลิสต์ซึ่งการเพิ่มข้อมูลจะกระทำที่ปลายข้างหนึ่งซึ่ง
เรียกว่าส่วนท้ายหรือเรียร์ (rear) และการนำข้อมูลออกจะ
กระทำที่ปลายอีกข้างหนึ่งซึ่งเรียกว่า ส่วนหน้า หรือฟรอนต์
(front)
ลักษณะการทำงานของคิวเป็นลักษณะของการเข้าก่อน
ออกก่อนหรือที่เรียกว่า FIFO (First In First Out)
การทำงานของคิว
การใส่สมาชิกตัวใหม่ลงในคิว เรียกว่า Enqueue

ซึ่งมีรูปแบบคือ
enqueue (queue, newElement)
หมายถึง การใส่ข้อมูลnewElement ลงไปที่ส่วนเรียร์ของคิว
การนำสมาชิกออกจากคิว เรียกว่าDequeue
ซึ่งมีรูปแบบคือ
dequeue (queue, element)หมายถึง การนำออกจากส่วนหน้า
ของคิวและให้ ข้อมูลนั้นกับ element
การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดงจะ
เรียกว่า Queue Front
แต่จะไม่ทำการเอาข้อมูลออกจากคิว
การนำข้อมูลที่อยู่ตอนท้าย
ของคิวมาแสดงจะ เรียกว่า
Queue Rear แต่จะไม่ทำ
การเพิ่มข้อมูลเข้าไปในคิว
การแทนที่ข้อมูลของคิว
สามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์
2. การแทนที่ข้อมูลของคิวแบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
จะประกอบไปด้วย 2 ส่วน คือ
1. Head Node
จะประกอบไปด้วย 3 ส่วนคือ
พอยเตอร์จำนวน 2 ตัว คือ Front และ rear
กับจำนวนสมาชิกในคิว
2. Data Node จะประกอบไปด้วย
ข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป

การดำเนินการเกี่ยวกับคิว

1.Create Queue คือ จัดสรรหน่อยความจำให้แก่ Head Node

และให้ค่า ponter ทั้ง 2 ตัวมีค่าเป็น null และจำนวนสมาชิกเป็น 0

2.Enqueue คือ การเพื่มข้อมูลเข้าไปใน

3.Dequeue คือ การนำข้อมุลออกจากคิว

4.Queue Front คือ เป็นการนำข้อมูลที่อยู่ส่วนต้นของคิวมาแสดง

5.Queue Rear คือ เป็นการนำข้อมุลที่อยุ่ส่วนท้ายของคิวมาแสดง

6.Empty Queue คือ เป็นการตรวจสอบว่าคิวว่างหรือไม่

7.Full Queue คือ เป็นการตรวจสอบว่าคิวเต็มหรือไม่

8.Queue Count คือ เป็นการนับจำนวนสมาชิกที่อยู่ในคิว

9.Destroy Queue คือ เป็นการลบข้อมุลทั้งหมดที่อยู่ในคิว
การประยุกต์ใช้คิว
คิวถูกประยุกต์ใช้มากในการจำลองระบบงาน
ธุรกิจ เช่น การให้บริการลูกค้า ต้องวิเคราะห์จำนวน
ลูกค้าในคิวที่เหมาะสม
ว่าควรเป็นจำนวนเท่าใด เพื่อให้ลูกค้าเสียเวลาน้อย
ที่สุด ในด้านคอมพิวเตอร์ ได้นำคิวเข้ามาใช้ คือ
ในระบบปฏิบัติการ (Operation System) ในเรื่อง
ของคิวของงานที่เข้ามาทำงาน (ขอใช้ทรัพยากร
ระบบของ CPU) จะจัดให้งานที่เข้ามาได้ทำงาน
ตามลำดับความสำคัญ