Data Structure and Algorithm

35 ก็จะต่อกันไปจนกระทั่งถึง Q[10] และเมื่อต้องการดึงเอาข้อมูลออกจากคิวก็จะกระทาในส่วนหัวนั่น คือส่วน front เม่ือนาออกในตาแหน่ง Q[1] แลว้ และต้องการนาออกอีกก็จะมีการไล่ตามลาดับภาพที่ 3.7 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 5 EFGH I J rear= 10 front rear ภาพที่ 3.7 การ Dequeue จากภาพที่ 3.7 การ Dequeue ข้อมูลจะเร่ิมต้นดาเนินการท่ีตาแหน่ง front โดยการ Dequeue ในตาแหน่งของ front ก็เปลี่ยนเป็น front = Q[2]=B และหาก Dequeue ข้อมูลอีก ตาแหนง่ front ก็จะเปลย่ี นแปลงไปเรื่อย ๆ 3.3.2 การด้าเนินการแทนควิ ดว้ ยอารเ์ รย์ 1. เพ่มิ ขอ้ มูลลงในคิว (Enqueue) โดยขอ้ มูลจะเพิ่มเข้ามาทางด้าน rear ของคิว - insert (q,A); เขยี นแทนความหมายของการเพิม่ ข้อมลู A ผา่ นทาง rear เขา้ มายังคิวช่อื q [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 1 A rear= 1 front rear - insert (q,B); เขียนแทนความหมายของการเพ่มิ ขอ้ มูล B ผ่านทาง rear เขา้ มายังควิ ชือ่ q [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 1 AB rear= 2 front rear - insert (q,C); เขยี นแทนความหมายของการเพิ่มขอ้ มูล C ผา่ นทาง rear เขา้ มายังควิ ชอ่ื q [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 1 ABC rear= 3 front rear เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมลู และอัลกอริทึม

36 - insert (q,D); เขียนแทนความหมายของการเพ่มิ ขอ้ มูล D ผา่ นทาง rear เข้ามายังควิ ชอ่ื q [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 1 ABCD rear= 4 front rear - insert (q,E); เขียนแทนความหมายของการเพ่ิมข้อมูล E ผ่านทาง rear เข้ามายังคิวชือ่ q [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 1 ABCDE rear= 5 front rear 2. ดึงข้อมูลออกจากคิว (Dequeue) ขอ้ มูลจะถูกดึงออกจากคิวผ่านทาง front ถ้า ขอ้ มูลทอี่ ย่ภู ายในคิวมเี พยี งตัวเดยี ว คา่ front จะมคี ่าเท่ากบั rear (อยใู่ นตาแหนง่ เดียวกนั ) - remove (q); เขียนแทนความหมายของการดงึ ข้อมูล A ออกจากควิ q ทางดา้ น front [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 1 ABCDEFGH I J rear= 10 front rear - remove (q); เขียนแทนความหมายของการดึงข้อมลู B ออกจากควิ q ทางดา้ น front [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 2 BCDEFGH I J rear= 10 front rear - remove (q); เขียนแทนความหมายของการดงึ ข้อมูล C ออกจากคิว q ทางด้าน front [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 3 CDEFGH I J rear= 10 front rear เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มลู และอัลกอรทิ มึ

37 - remove (q); เขียนแทนความหมายของการดึงข้อมลู D ออกจากควิ q ทางดา้ น front [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 4 DEFGH I J rear= 10 front rear - remove (q); เขียนแทนความหมายของการดึงขอ้ มูล E ออกจากคิว q ทางด้าน front [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 5 EFGH I J rear= 10 front rear 3. ตรวจสอบว่ามีข้อมูลอยู่ภายในคิวหรือไม่ (Empty หรือ Underflow) จะไม่ สามารถดึงข้อมูลออกจากคิวว่าง หรือคิวที่ไม่มีข้อมูลใดได้ ดังนั้นต้องมีการตรวจสอบคิวว่าง คือ empty (q); ถ้าควิ ช่อื q ว่างไมม่ ีข้อมูลอยู่ภายในนนั้ จะได้คา่ ออกมาเปน็ True แต่ถา้ ภายในคิวมขี ้อมูล อยจู่ ะได้คา่ ออกมาเป็น False 4. ตรวจสอบว่ามีข้อมูลอยู่ภายในคิวเต็มหรือไม่ (Full หรือ Overflow) การ ดาเนินการนี้มักตรวจสอบเม่ือต้องการเพ่ิมข้อมูลลงไปในคิว และต้องมีการตรวจสอบก่อนว่าคิวเต็ม หรือไม่ มีเน้อื ที่ทจี่ ะใสข่ ้อมูลลงไปได้หรอื ไม่ เสร็จแล้วจึงใสข่ อ้ มูลลงไปได้ ตัวอย่างท่ี 3.1 จงแสดงภาพการสร้างคิวด้วยอาร์เรย์ (Q) และข้ันตอนการเก็บค่าลงในคิวตามลาดับ คือ insert (Q,C), insert (Q,O), insert (Q,M), remove (Q), remove (Q), insert (Q,P), insert (Q,U), insert (Q,T), remove (Q), remove (Q) - insert (Q,C); เขยี นแทนความหมายของการเพิม่ ขอ้ มูล C ผ่านทาง rear เขา้ มายังควิ ชอ่ื Q [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 1 C rear= 1 front rear เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมลู และอลั กอริทึม

38 - insert (Q,O); เขยี นแทนความหมายของการเพิ่มขอ้ มูล O ผา่ นทาง rear เข้ามายงั ควิ ชอื่ Q [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 1 CO rear= 2 front rear - insert (Q,M); เขียนแทนความหมายของการเพมิ่ ข้อมลู M ผา่ นทาง rear เขา้ มายังคิวช่ือ Q [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 1 COM rear= 3 front rear - remove (Q); เขียนแทนความหมายของการดึงขอ้ มลู C ออกจากคิว Q ทางดา้ น front [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 2 OM rear= 3 front rear - remove (Q); เขยี นแทนความหมายของการดงึ ข้อมลู O ออกจากควิ Q ทางดา้ น front [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 3 M rear= 3 front rear - insert (Q,P); เขยี นแทนความหมายของการเพิ่มขอ้ มูล P ผ่านทาง rear เขา้ มายงั ควิ ชือ่ Q [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 3 MP rear= 4 front rear - insert (Q,U); เขียนแทนความหมายของการเพ่มิ ขอ้ มลู U ผา่ นทาง rear เขา้ มายังควิ ชอื่ Q เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมลู และอลั กอรทิ มึ

39 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 3 MPU rear= 5 front rear - insert (Q,T); เขียนแทนความหมายของการเพิม่ ขอ้ มลู T ผ่านทาง rear เขา้ มายังคิวชื่อ Q [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 3 MPUT rear= 6 front rear - remove (Q); เขียนแทนความหมายของการดึงข้อมูล M ออกจากคิว Q ทางดา้ น front [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 4 PUT rear= 6 front rear - remove (Q); เขยี นแทนความหมายของการดงึ ข้อมูล P ออกจากคิว Q ทางดา้ น front [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 5 UT rear= 6 front rear เกิดปัญหาความต้องการ Enqueue ข้อมูลเข้าอีก แต่คิวไม่สามารถท่ีจะ Enqueue ข้อมูลเข้าได้เพราะคิวจะระบุ rear = maxsize หมายถึง พื้นท่ีในการจัดข้อมูลเต็ม หรอื Queue Full แต่ในความเป็นจริงแล้วยังเหลือพื้นที่ในส่วนหน้าอีก ดังน้ันจึงมีการแก้ปัญหาของคิวนี้ด้วยการกาหนด ควิ วงกลม (Circular Queue) เพอ่ื ทจี่ ะไดส้ ามารถใช้พื้นที่สว่ นหน้าได้ 3.3.3 การดา้ เนนิ การแทนควิ ดว้ ยวงกลม (Circular Queue) การใช้คิววงกลมสามารถแก้ปัญหาการมีพื้นที่ว่างในส่วนหัวของคิว ซึ่งทาให้สามารถ Enqueue ขอ้ มลู เขา้ มายังคิวได้จนกว่าคิวเต็มจรงิ ๆ เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมลู และอัลกอรทิ ึม

40 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 5 EFGH I J rear= 10 Front rear ภาพที่ 3.8 แทนควิ ด้วยวงกลม จากภาพท่ี 3.8 สามารถแสดงลักษณะของคิวแบบวงกลม เพื่อให้เกิดความเข้าใจได้ง่าย ดัง ภาพท่ี 3.9 rear 8 1 2 H 7G 6F 3 E 4 front 5 ภาพที่ 3.9 คิวแบบวงกลม จากภาพที่ 3.9 ลักษณะของโครงสร้างของคิววงกลมจะมีการนาเอาคิวท้ายมาเช่ือมต่อกับคิว ส่วนหัวและเมื่อมีการ Enqueue ข้อมูลเข้าจะดาเนินการต่อไปในส่วนของ rear โดยมีทิศทางใน ลักษณะของการเดินตามเขม็ นาฬิกาหรอื จากซ้ายไปขวา เมื่อมีการ Enqueue ขอ้ มูลเขา้ มาอีกกจ็ ะเพ่ิม ต่อทา้ ยไปและเซตพอยน์เตอร์ ชไี้ ปยงั ตาแหน่ง Q[1] ดังภาพที่ 3.10 เชน่ เดียวกนั หากมกี าร Dequeue ขอ้ มูลกจ็ ะกระทาทางตาแหน่ง front ทาใหส้ ามารถใชง้ านพืน้ ทว่ี ่างบนควิ ได้ ดงั ภาพที่ 3.11 เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมลู และอัลกอริทึม

41 8 1 rear K 2 H 7G 6F 3 E 4 front 5 ภาพท่ี 3.10 Enqueue 81 rear 2 HK 7G front 6 F 3 54 ภาพที่ 3.11 Dequeue นอกจากนี้ยังสามารถตรวจสอบว่าคิวน้ันเต็มหรือไม่ จากการชี้ตาแหน่งของ rear และ front ซึ่งค่าข้อมูลท่ีติดกันดังภาพท่ี 3.12 แต่ในบางครั้งการตรวจสอบจากตาแหน่งข้อมูลของ rear และ front ก็ไม่สามารถบอกได้ว่าคิวน้ันเต็มเสมอไป เน่ืองจากมีการ Dequeue ข้อมูลออกแต่รูปแบบของ การชี้คา่ มลี กั ษณะเชน่ เดยี วกบั ควิ เตม็ ดังภาพท่ี 3.13 เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มูลและอัลกอรทิ มึ

42 rear 8 1 front HA 7G B2 6F ED C3 54 ภาพที่ 3.12 ควิ เตม็ rear 8 1 front 2 H I 7G 6F 3 E 54 ภาพท่ี 3.13 ควิ วา่ ง เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมลู และอัลกอริทมึ

43 ชือ่ หน่วยเรียน : สแตก (Stack) รหสั วิชา 13-132-207 หนว่ ยเรียนท่ี 4 เวลาสอน 6 คาบ ชอ่ื บทเรียน 4.1 โครงสรา้ งสแตก 4.2 การดาเนนิ การของสแตก 4.3 การแทนสแตกดว้ ยอารเ์ รย์ จุดประสงค์การสอน 4.1 รู้โครงสรา้ งสแตก 4.1.1 บอกลกั ษณะโครงสรา้ งสแตก 4.2 เข้าใจพน้ื ฐานการดาเนนิ การกับสแตก 4.2.1 อธบิ ายการนาเขา้ ข้อมลู (push) 4.2.2 อธบิ ายการดึงข้อมลู ออก (pop) 4.2.3 อธบิ ายตาแหน่งบนสดุ (top) 4.3 เขา้ ใจการแทนสแตกด้วยอาร์เรย์ 4.3.1 หาผลลัพธ์การแทนสแตกด้วยอาร์เรย์ 4.3.2 แกป้ ญั หาการประยุกตใ์ ชง้ านสแตกในการแปลงรปู นิพจน์ทางคณิตศาสตร์ เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มลู และอัลกอริทึม

44 หนว่ ยเรียนท่ี 4 สแตก (Stack) สแตกเป็นโครงสร้างข้อมูลที่มีคุณสมบัติการนาข้อมูลเข้าและดึงข้อมูลออกได้จากตาแหน่ง เดียวกัน โดยจะต้องกระทา ณ ตาแหน่งบนสุดของสแตก คือ ตาแหน่งท่ี top ช้ีอยู่เท่าน้ัน หาก ต้องการนาข้อมูลออกจากสแตก ข้อมูลน้ันจะต้องเป็นข้อมูลท่ีเข้ามาหลังสุด หรือเรียกว่า เข้าทีหลัง ออกก่อน เช่น การวางจานซ้อน ๆ กัน หากต้องการหยิบจานออกมา 1 ใบ จาเป็นต้องเลือกจานที่อยู่ บนสดุ หรือจานท่วี างทหี ลงั นนั้ เอง 4.1 โครงสร้างสแตก (Stack structure) สแตกเป็นโครงสร้างที่ถูกออกแบบมาให้มีลักษณะท่ีเป็นเชิงเส้น (Linear list) การเข้าออก ของข้อมูล หากข้อมูลใดเข้ามาทีหลังก็จะออกก่อน เรียกลักษณะการดาเนินการแบบน้ีว่า Last in First Out (LIFO) หรือ เข้าทีหลังออกก่อน เมื่อมีการนาเข้าข้อมูล เรียกว่า push และการดึงข้อมูล ออก เรยี กว่า pop โดยโครงสรา้ งจะการกระทาในตาแหน่งบนสดุ เรยี กว่า top 50 40 30 20 10 a 25 20 15 25 top 25 20 20 15 15 10 10 55 push pop ภาพท่ี 4.1 การทางานของโครงสร้างสแตก จากภาพท่ี 4.1 เปน็ การนาข้อมลู เข้าสแตก เรียกวา่ push จะนาเข้าขอ้ มูลเรยี งตามลาดบั โดย จัด 5 เข้าอยู่ที่ตาแหน่งล่างสุด และค่าสุดท้ายตาแหน่ง top คือ 25 สาหรับการดึงข้อมูลออกจาก สแตก เรียกว่า pop จะกระทาจากตาแหน่ง top คอื นาขอ้ มูล 25 ออกมาเป็นอันดับแรก หากต้องการ นาออกอีกตาแหน่ง top คือ 20, 15 นาออกมาเป็นอันดับท่ีสองและสาม เมื่อไม่ต้องการดึงข้อมูลออก จากตาแหนง่ top ก็คือ 10 โครงสรา้ งสแตกมลี ักษณะ (วิวฒั น์ อภสิ ิทธิ์ภิญโญ และอมร มสุ กิ สาร, 2550 : 123) ดังนี้ 1. โครงสร้างข้อมูลเป็นแบบเชิงเส้น (Linear structure) ลักษณะโครงสร้างจะ จัดเรียงต่อเนอื่ งกันไป ซ่ึงถือเป็นโครงสร้างในรูปแบบของอารเ์ รย์และเรคอรด์ เอกสารประกอบการสอนรายวชิ าโครงสร้างขอ้ มลู และอลั กอริทมึ

45 2. มีลักษณะโครงสร้างที่ไม่ตายตัว (Dynamic structure) สามารถปรับเปลี่ยน จานวนสมาชิกในโครงสร้างได้ ขณะท่ีมีการทางานอยู่ แต่ถ้าเป็นการใช้ในโครงสร้างของอาร์เรย์ จาเปน็ ต้องมกี ารกาหนดพ้ืนทีก่ ารจองบนหน่วยความจาทเี่ หมาะสม 3. น้าข้อมูลเข้าและดึงข้อมูลออกได้ (push and pop) สามารถที่จะทาการ push และ pop สลบั กันไปมาได้ ไมจ่ าเป็นที่จะต้องนาข้อมูลเข้าอย่างเดียว หรอื ดึงข้อมูลออกทง้ั หมด พร้อมกัน เพราะถือว่าแต่ละข้อมูลแยกกันตามโครงสร้างท่ีออกแบบมาเพื่อจัดเก็บ แต่สาหรับการนา ข้อมูลเข้าหรือนาข้อมูลออกน้ัน อาจเกิดข้อผิดพลาดขึ้นได้กรณีท่ีสแตกน้ันเต็มแล้ว นาข้อมูลเข้าไปอีก จะเกิดการผิดพลาดท่ีเรยี กว่า stack overflow หรือหากเป็นการนาข้อมูลออกโดยท่ีภายในสแตกไม่มี ขอ้ มลู อยู่เลย เรยี กความผดิ พลาดนี้ว่า stack underflow 4. น้าข้อมูลเข้าและดึงข้อมูลออกแบบล้าดับ (LIFO mechanism) เมื่อต้องการ นาข้อมูลเข้าหรือออกจากสแตกจะต้องนาออกตามการเรียงที่เป็นลาดับ ไม่ข้าม หรือกระโดดไปเอา ข้อมูลใดขอ้ มลู หนง่ึ กอ่ น 5. มีการจัดการน้าเข้าและดึงข้อมูลในต้าแหน่งบนสุด (push and pop at top) การจัดการต่าง ๆ อันได้แก่ การนาข้อมูลเข้าและการดึงข้อมูลออกจะต้องกระทา ณ ตาแหน่งบนสุด เท่าน้นั 4.2 การด้าเนนิ การของสแตก ลักษณะของการดาเนินการในโครงสร้างแบบสแตก ประกอบดว้ ย 3 กรณี คือ 4.2.1 การน้าเข้าข้อมูล (push) คือ การเพิ่มข้อมูลลงในสแตก กรณีท่ีไม่มีข้อมูลใดอยู่ก็จะ push เข้าไปเป็นตาแหน่งแรก ซงึ่ ถือวา่ ข้อมูลน้ีเป็นตาแหน่ง top แต่ถ้าหากนาข้อมูล push เข้ามาอีก ก็จะดาเนินการจัดลงในตาแหน่งต่อจาก top และปรับค่า top มาอยู่ที่ข้อมูลท่ี push เข้าไปใหม่ แต่ ต้องมีการตรวจสอบก่อนว่าสแตกเต็ม (stack overflow) หรือไม่ ลักษณะของการ push แสดงดัง ภาพที่ 4.2 กอ่ น หลงั 20 push 20 top top 15 15 10 10 5 5 ภาพที่ 4.2 การดาเนินการ push ขอ้ มูล เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มลู และอลั กอริทึม

46 จากภาพท่ี 4.2 เริ่มแรกสแตกมีข้อมูลอยู่ 2 ชุด ตาแหน่งของ top จะอยู่ท่ี 15 เม่ือต้องการ push 20 เข้ามายังสแตกผ่านการ push ก็จะทาให้ 20 เข้ามาอยู่ในสแตก และมีการปรบั top ใหมอ่ ยู่ ท่ี 20 แทน 4.2.2 การดึงข้อมูลออก (pop) คือ การนาข้อมูลออกจากสแตก ซ่ึงการดาเนินการก็จะต้อง ดาเนินในตาแหน่ง top กรณีของการ pop ต้องตรวจสอบก่อนว่า สแตกว่าง (stack under flow) หรอื ไม่ จงึ จะสามารถนาข้อมลู ออกจากสแตกได้ ลักษณะของการ pop แสดงดังภาพที่ 4.3 กอ่ น หลงั 20 Top 20 pop 15 10 15 top 5 10 4 ภาพที่ 4.3 การดาเนินการ pop ขอ้ มลู จากภาพท่ี 4.3 เริ่มแรกสแตกมีข้อมูลอยู่ 2 ชุด ตาแหน่งของ top จะอยู่ท่ี 20 เม่ือต้องการ pop ขอ้ มลู ออกจากสแตก กจ็ ะ pop 20 ออกและมกี ารปรบั top ใหม่อยู่ท่ี 15 แทน 4.2.3 ต้าแหน่งบนสุด (top) คือ ตาแหน่งบนสุดของสแตก หากต้องการ pop หรือ push ข้อมูลจะต้องทา ณ ตาแหน่งน้ี โดยลักษณะการดาเนินการของ top เป็นเพียงส่ิงท่ีบอกตาแหน่งของ ข้อมูลที่อยู่บนสุดเท่าน้ัน หากมีการ push ข้อมูลตาแหน่งของ top ก็จะชี้ค่าไปท่ีตาแหน่งสูงสุดใหม่ คอื top = top+1 และหากมีการ pop ขอ้ มูลออกไป top กไ็ ม่ใช่ตวั ดาเนนิ การในการลบค่าแต่จะเป็น การคืนค่าและลดตาแหน่งลงมา คือ top = top -1 ซ่ึง top จะเกิดความผิดพลาดกรณีเดียวกันกับ pop ก็คอื underflow เมอื่ สแตกน้นั เกดิ การว่าง ดังภาพที่ 4.4 ก่อน หลัง 20 stack top 20 15 Top 15 10 10 5 5 ภาพที่ 4.4 การดาเนินการ top ขอ้ มลู เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มูลและอลั กอริทมึ

47 4.3 การแทนสแตกดว้ ยอาร์เรย์ การนาเอาอาร์เรยเ์ ข้ามาใช้งานในการกาหนดโครงสร้างหรอื แทนที่ข้อมูลในสแตก ซึ่งลักษณะ เฉพาะตัวของโครงสร้างอาร์เรย์เป็นโครงสร้างท่ีสามารถกาหนดจองพ้ืนที่บนหน่วยความจาได้แน่นอน และสามารถเก็บข้อมูลท่ีเป็นชนิดเดียวกัน และมีตัวแปรในการเก็บตาแหน่งบนสุดของสแตก คือ top โดยข้อดี คือ ง่ายและสะดวกต่อการใช้งานและการสรา้ ง แต่ข้อจากัด คือ ประกาศหน่วยความจาแล้ว ไม่สามารถเพิม่ ขนาดหนว่ ยความจาไดอ้ กี ตารางท่ี 4.1 รายชอื่ นกั เรียนสาหรับจัดในโครงสร้างสแตกด้วยอาร์เรย์ ลา้ ดบั รายช่ือนกั เรยี น พ้ืนทีว่ า่ ง STUDENT 10 1 SITA สาหรบั push : : 2 PORNPIT : : 3 CHAN : 5 4 KITTIWIT 4 5 NATCHA NATCHA 3 :: KITTIWIT 2 :: CHAN 1 10 RANIDA PORNPIT SITA จากตารางท่ี 4.1 จากการนาข้อมูลเข้า จานวน 4 รายชื่อ นาเข้า ข้อมูลแรกคือ SITA ข้อมูลท่ี 2 คือ PORNPIT ข้อมูลท่ี 3 คือ CHAN ข้อมูลที่ 4 คือ KITTIWIT จัดอยู่ในอาร์เรย์ student[1], [2], [3] และ [4] ตามลาดับ ในขณะนีค้ ่า top คือ NATCHA 4.3.1 การด้าเนนิ การแทนสแตกดว้ ยอาร์เรย์ การดาเนินการแทนสแตกด้วยอารเ์ รย์ มีการทางานพื้นฐานประกอบด้วย 4 ประการ คอื 1. เพมิ่ ข้อมูลลงในสแตก (Push) - push (s,A) คือ การเพมิ่ ข้อมูล ‘A’ ลงในสว่ น top ของสแตก s ดังภาพท่ี 4.5(a) - push (s,B) คือ การเพมิ่ ข้อมลู ‘B’ ลงในสว่ น top ของสแตก s ดงั ภาพท่ี 4.5(b) - push (s,C) คือ การเพิม่ ข้อมลู ‘C’ ลงในสว่ น top ของสแตก s ดังภาพที่ 4.5(c) - push (s,D) คือ การเพ่มิ ขอ้ มูล ‘D’ ลงในส่วน top ของสแตก s ดังภาพที่ 4.5(d) top D [4] top C [3] C [3] top B [2] B [2] B [2] top A [1] A [1] A [1] A [1] (a) (b) (c) (d) เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมูลและอัลกอริทึม

48 2. ลบข้อมูลลงในสแตก (Pop) - pop(s) คือ การดึงข้อมลู จาก top ของสแตก s น่ันกค็ ือ E ดงั ภาพท่ี 4.6(a) - pop(s) คอื การดงึ ขอ้ มลู จาก top ของสแตก s นน่ั ก็คอื D ดังภาพท่ี 4.6(b) - pop(s) คือ การดงึ ขอ้ มูลจาก top ของสแตก s น่นั กค็ อื C ดงั ภาพท่ี 4.6(c) E [5] Top top top top D [4] D [4] C [3] B [2] C [3] C [3] B [2] A [1] B [2] B [2] A [1] (d) A [1] A [1] (c) (a) (b) ภาพที่ 4.6 การลบขอ้ มูลออกจากสแตก (pop) 3. ตรวจสอบว่ามีข้อมูลอยู่ภายในสแตกหรือไม่ (Empty) ส่วนใหญ่แล้วมักใช้ร่วมกับ pop(s) เน่ืองจากจะไม่สามารถดึงข้อมูลออกมาจากส แตกว่างหรือสแตกท่ีไม่มีข้อมูลใด ๆ อยู่ได้ ดังน้ันจึงต้องตรวจสอบดูก่อนว่ามีข้อมูลอยู่ในสแตกหรือไม่ ก่อนทจี่ ะดงึ ขอ้ มูลออกมาจากสแตก 4.3.2 การประยกุ ต์ใช้งานสแตกในการแปลงรูปนิพจน์ทางคณติ ศาสตร์ หลักการทางานของสแตกเป็นการทางานในลักษณะของการกลับด้าน คอื สามารถท่ีจะทราบ ผลลัพธ์ก็ต่อเม่ือ นาเข้ามูลนั้นออกมาจากสแตกแล้ว และบ่อยคร้ังท่ีคอมพิวเตอร์นาเอาคุณสมบัตินี้ไป ใช้คานวณดว้ ยการนาเขา้ ข้อมูลทกุ ตัวแล้ว จึงทาการประมวลผลลัพธ์ออกมา เม่ือมีการนาเขา้ ข้อมูลเข้า สู่สแตก สแตกจะทาการแปลงรปู นพิ จนเ์ พอื่ ให้เหมาะแก่การคานวณสาหรับระบบคอมพิวเตอร์ 1. นพิ จนท์ างคณติ ศาสตรท์ ั่วไป แบ่งออกเป็น 3 ประเภทคอื (1) ตวั ดาเนนิ การ (Operator) คือ เคร่ืองหมายคานวณตา่ งๆ ไดแ้ ก่ + - * / (2) ตัวถกู ดาเนนิ การ (Operand) คอื ตัวแปรหรอื คา่ คงที่ ได้แก่ A B C 1 2 2. รปู แบบนพิ จน์ทางคณิตศาสตร์ แบ่งออกเปน็ 3 ประเภทคือ (1) นิพจน์ Infix คือ นิพจน์ที่มีเครื่องหมายดาเนินการ (Operator) อยู่ กงึ่ กลางตวั ถกู ดาเนนิ การ (Operand) เช่น A+B (2) นิพจน์ Postfix คือ นิพจน์ท่ีมีเคร่ืองหมายดาเนินการ (Operator) อยู่ ดา้ นหลงั ตวั ถกู ดาเนนิ การ (Operand) เชน่ AB+ (3) นิพจน์ Prefix คือ นิพจน์ท่ีมีเครื่องหมายดาเนินการ (Operator) อยู่ ดา้ นหน้าตัวถูกดาเนินการ (Operand) เช่น +AB 3. ลา้ ดับความส้าคัญของตวั ด้าเนินการ ตัวดาเนินการท่ีมีความสาคัญมากกว่าตัวดาเนินการอ่ืน ๆ ที่อยใู่ นนิพจน์เดียวกัน จะ ถูกประมวลผลก่อน แต่ถ้ามีตัวดาเนินการท่ีมีลาดับความสาคัญเท่ากัน หากไม่มีการกาหนดวงเล็บให้ เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มูลและอัลกอริทึม

49 เทียบลาดับความสาคัญจากซ้ายมือไปขวา ยกเว้นเลขยกกาลังลาดับความสาคัญจากขวาไปซ้ายมือ โดยลาดับความสาคัญของตัวดาเนินการสามารถแสดงได้ดงั ตารางท่ี 4.2 ตารางที่ 4.2 ลาดับความสาคัญของตวั ดาเนินการ ลา้ ดับความส้าคญั ตัวดา้ เนินการ คา้ อธิบาย 1 () เครอ่ื งหมายวงเล็บ 2 ^ ยกกาลัง 3 */ คูณ หาร 4 +- บวก ลบ 4. การแปลงนพิ จน์ Infix ให้เป็น Postfix การดาเนินการด้านคานวณ ในระบบคอมพิวเตอร์ไม่สามารถท่ีจะจัดลาดับของการ คานวณในรูปแบบของ infix ได้ แต่จะแปลงเป็นนิพจน์ของ Postfix หรือ Prefix เสียกอ่ น โดยลักษณะ ของการแปลงนิพจน์จะใช้การเปรียบเทียบความสาคัญของตัวดาเนินการและหลักการอัลกอริทึมของ การแปลงนพิ จน์ 5. อลั กอรทิ ึมสา้ หรบั การแปลงนิพจน์ การแปลงนิพจน์น้ันสามารถท่ีจะดาเนินการแปลงนิพจน์ Infix ให้เป็นได้ทั้ง Prefix และ Postfix แต่โดยระบบทีน่ ยิ มใช้กนั โดยท่วั ไปจะใช้เพยี งแต่การแปลงนพิ จน์ Infix เปน็ Postfix 6. การด้าเนนิ การในการแปลงนิพจน์ Infix ให้เปน็ Postfix 1) ถ้าข้อมูลเข้า (input) เป็นตัวถูกดาเนินการ (operand) ใหน้ าออกไปเป็น ผลลัพธ์ (output) 2) ถ้าขอ้ มูลเข้าเป็นตวั ดาเนินการ (operator) ให้ดาเนนิ การดงั น้ี 2.1 ถ้าสแตกวา่ ง ให้ push ตัวดาเนินการลงในสแตก 2.2 ถ้าสแตกไม่ว่าง ให้เปรียบเทียบตัวดาเนินการท่ีเข้ามากับตัว ดาเนนิ การทอ่ี ยูใ่ นตาแหนง่ top ของสแตก 2.2.1 ถ้าตัวดาเนินการท่ีเข้ามามีความสาคัญมากกว่าตัว ดาเนินการท่ีตาแหนง่ top ของสแตกให้ push ลงสแตก 2.2.2 ถ้าตัวดาเนินการท่ีเข้ามามีความสาคัญนอ้ ยกว่าหรือ เทา่ กบั ตัวดาเนนิ การที่อยใู่ นตาแหนง่ top ของสแตก ให้ pop สแตกออกไปเป็นผลลพั ธ์ 3) พจิ ารณาเคร่อื งหมายวงเล็บ 3.1 กรณีเป็นวงเลบ็ เปดิ ให้ push เกบ็ ลงในสแตก 3.2 กรณีเป็นวงเล็บปิด ดาเนินการ pop ตัวดาเนินการออกจาก สแตกจนกว่าจะพบวงเลบ็ เปดิ และยกเลิกเคร่อื งหมายวงเล็บปิด 4) พิจารณานิพจน์ เมื่อนาเอาตัวถูกดาเนินการออกเป็นผลลัพธ์ทุกตัว ตรวจสอบสแตกหากมตี ัวถกู ดาเนนิ การเหลืออยู่ให้ pop ออกให้หมดจนกวา่ สแตกวา่ ง เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มลู และอลั กอริทึม

50 ตวั อยา่ งท่ี 4.1 จงแปลงนพิ จน์ Infix ของ A-B/C*D^E ใหเ้ ปน็ นิพจน์ Postfix นพิ จน์ Infix Stack เกบ็ ตวั ด้าเนนิ การ นพิ จน์ Postfix A วา่ ง A - - A B - AB / -/ AB C -/ ABC * -* ABC/ D -* ABC/D ^ -*^ ABC/D E -*^ ABC/DE ว่าง -* ABC/DE^ ว่าง - ABC/DE^* วา่ ง วา่ ง ABC/DE^*-  นิพจน์ Infix ของ A-B/C*D^E แปลงเปน็ นพิ จน์ Postfix คือ ABC/DE^*- ตวั อย่างที่ 4.2 จงแปลงนพิ จน์ Infix ของ A*B/C+(D-E)+F ใหเ้ ปน็ นพิ จน์ Postfix นิพจน์ Infix Stack เก็บตัวดา้ เนนิ การ นพิ จน์ Postfix A ว่าง A * * A B * AB / / AB* C / AB*C + + AB*C/ ( +( AB*C/ D +( AB*C/D - +(- AB*C/D E +(- AB*C/DE ) + AB*C/DE- + + AB*C/DE-+ F + AB*C/DE-+F ว่าง ว่าง AB*C/DE-+F+ เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มูลและอลั กอริทึม

51  นิพจน์ Infix ของ A*B/C+(D-E)+F แปลงเปน็ นิพจน์ Postfix คอื AB*C/DE-+F+ 5. การหาผลลัพธ์จากนิพจน์ Postfix สาหรบั การหาผลลัพธ์จากนพิ จน์ Postfix นัน้ จะเปน็ การหาผลลัพธ์ท่แี ตกตา่ งไปจาก นิพจน์ของ Infix เพราะมีการวางรูปแบบท่ีแตกต่างกัน แต่อย่างไรก็ตามผลลัพธ์ที่ออกมาจะต้องมีค่า เทา่ กันเสมอ ซึ่งหลักการของการหาผลลพั ธ์ คอื 5.1 ถา้ เปน็ ตัวถูกดาเนินการให้ push ลงสแตก 5.2 ถ้าเปน็ ตวั ดาเนินการให้ pop ตัวดาเนนิ การออกจากสแตก 2 ตัวแลว้ หา ค่าผลรวมที่ดาเนินการด้วยตัวดาเนินการน้ัน แล้วเก็บผลรวมลงสแตกดาเนินการกับตัวดาเนินการ ตอ่ ไปจนกวา่ จะหมดตวั ดาเนินการ ตวั อยา่ งที่ 4.3 จงหาผลลพั ธข์ องนิพจน์ Postfix ABC/DE^*- เม่อื A=3, B=4, C=8, D=6, E=2 นพิ จน์ Postfix Stack เก็บตวั ด้าเนนิ การ ผลลัพธ์ 3 3 ว่าง 4 34 ว่าง 8 348 ว่าง / 3 (4/8) วา่ ง 6 326 วา่ ง 2 3262 วา่ ง ^ 3 2 (6^2) วา่ ง * 3 (2*36) วา่ ง - (3-72) -69 ตรวจสอบการแทนคา่ ในนิพจนข์ อง Infix คอื 3-((4/8)*(6^2))= 3- ((2)*(36)) = 3-72 = -69 แสดงให้ทราบว่านิพจน์ของ Postfix ท่ีแปลงจากนิพจน์ Infix นั้นถูกต้องเพราะได้ค่า ของผลลพั ธท์ ่ีเท่ากัน เอกสารประกอบการสอนรายวชิ าโครงสร้างขอ้ มูลและอลั กอริทมึ

52 ตัวอย่างที่ 4.4 จงหาผลลัพธ์ของนิพจน์ Postfix AB*C/DE-+F+ เมื่อ A=2, B=3, C=30, D=5, E=4, F=13 นพิ จน์ Postfix Stack เก็บตวั ด้าเนนิ การ ผลลัพธ์ 2 2 ว่าง 3 23 วา่ ง * (2*3) วา่ ง 30 6 30 วา่ ง / (6/30) วา่ ง 5 65 ว่าง 4 654 ว่าง - 6 (5-4) วา่ ง + (6+1) ว่าง 13 7 13 วา่ ง + (7+13) 20 ตรวจสอบการแทนค่าในนิพจน์ของ Infix คือ 2*3/30+(5-4)+13 = (2*3)/30+(5-4)+13 = (6/30)+1+13 = 5+1+13 = 20 แสดงให้ทราบว่านิพจน์ของ Postfix ท่ีแปลงจากนิพจน์ Infix น้ันถูกต้องเพราะได้ค่า ของผลลัพธท์ ีเ่ ท่ากัน ตัวอยา่ งที่ 4.5 จงแปลงนิพจน์ Infix A*3/B+(C+D^2)*E+F ใหเ้ ป็นนิพจน์ Postfix และจงหาผลลัพธ์ ของนพิ จน์ Postfix เมื่อ A=4, B=12, C=9, D=8, E=1, F=25 นิพจน์ Infix Stack เก็บตัวด้าเนนิ การ นิพจน์ Postfix A วา่ ง A * * A 3 * A3 / / A3* B / A3*B - + A3*B/ ( +( A3*B/ เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมลู และอลั กอริทึม

53 นพิ จน์ Infix Stack เก็บตวั ด้าเนนิ การ นพิ จน์ Postfix C +( A3*B/C + +(+ A3*B/C D +(+ A3*B/CD ^ +(+^ A3*B/CD 2 +(+^ A3*B/CD2 ) A3*B/CD2^+ * + A3*B/CD2^+ E +* A3*B/CD2^+E + +* A3*B/CD2^+E*+ F + A3*B/CD2^+E*+F ว่าง + A3*B/CD2^+E*+F+ + นพิ จน์ Postfix Stack เกบ็ ตัวดา้ เนนิ การ ผลลพั ธ์ 4 4 ว่าง 3 43 ว่าง * (4*3) ว่าง 12 12 12 ว่าง / (12/12) ว่าง 9 19 ว่าง 8 198 ว่าง 2 198 2 ว่าง ^ 1 9 (8^2) วา่ ง + 1 (9+64) ว่าง 1 1 73 1 ว่าง * 1 (73*1) ว่าง + (1+73) วา่ ง 25 74 25 วา่ ง + (74+25) 99  นิพจน์ Infix ของ A*3/B-(C+D^2)*E+F แปลงเปน็ นิพจน์ Postfix คอื A3*B/CD2^+E*-F+ เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มลู และอัลกอรทิ มึ

54 ตรวจสอบการแทนคา่ ในนิพจน์ของ Infix คอื (4*3)/12+(9+8^2)*1+25 = (12/12)+(9+64)*1+25 = 1+(73*1)+25 = (1+73)+25 = (74+25) = 99 แสดงให้ทราบว่านิพจน์ของ Postfix ที่แปลงจากนิพจน์ Infix นั้นถูกต้องเพราะได้ค่า ของผลลัพธท์ เี่ ท่ากัน เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมูลและอลั กอรทิ มึ

55 ชอื่ หน่วยเรียน : ไบนารที รี (Binary Tree) รหสั วิชา 13-132-207 หน่วยเรียนที่ 5 เวลาสอน 6 คาบ ชอ่ื บทเรียน 5.1 โครงสร้างทรี 5.2 ชนิดของทรี 5.3 การเขา้ ถงึ ข้อมลู ในไบนารีทรี 5.4 ทรกี บั การดาเนินการด้านนิพจน์ 5.5 การแทนโครงสร้างไบนารที รีแบบซีเควนเชียล 5.6 การแปลงทรีเปน็ ไบนารีทรี จุดประสงค์การสอน 5.1 รู้โครงสรา้ งทรี 5.1.1 บอกลกั ษณะโครงสรา้ งทรี 5.2 เข้าใจชนดิ ของทรี 5.2.1 อธบิ ายและหาผลลัพธ์ทรีท่วั ไป 5.2.2 อธบิ ายและหาผลลพั ธ์ไบนารีทรี 5.3 สร้างการเข้าถงึ ข้อมลู ในไบนารที รี 5.3.1 ยกตวั อยา่ งและหาผลลพั ธ์การเขา้ ถึงแบบพรีออรเ์ ดอร์ 5.3.2 ยกตวั อยา่ งและหาผลลพั ธ์การเขา้ ถงึ แบบอินออเดอร์ 5.3.3 ยกตวั อย่างและหาผลลัพธ์การเข้าถึงแบบโพสตอ์ อเดอร์ 5.4 แกป้ ญั หาทรีกบั การดาเนนิ การดา้ นนพิ จน์ 5.4.1 หาผลลัพธ์ทรกี ับการดาเนนิ การด้านนิพจน์ 5.5 แกป้ ญั หาการแทนโครงสร้างไบนารที รแี บบซเี ควนเชยี ล 5.5.1 หาผลลพั ธ์การแทนโครงสรา้ งไบนารีทรีแบบซเี ควนเชยี ล 5.6 สรา้ งการแปลงทรเี ปน็ ไบนารีทรี 5.6.1 หาผลลพั ธ์การแปลงทรเี ป็นไบนารีทรี เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมลู และอลั กอรทิ มึ

56 หนว่ ยเรียนที่ 5 ไบนารที รี (Binary Tree) ไบนารีทรีเป็นโครงสร้างข้อมูลท่ีมีคุณสมบัติการเช่ือมโยงกันเป็นระดับชั้น และมีข้อมูลที่ เรียกวา่ โหนด (node) โดยโหนดแรกหรือโหนดที่อยบู่ นสุดเรียกว่า Root Node เช่ือมโยงไปยังโหนด ระดับรองลงไป แต่ละระดับก็มีการเชื่อมโยงโหนดระดับต่อไป เรียกว่า Subtree โดยแบ่งออกเป็นทรี (tree) และไบนารที รี (binary tree) 5.1 โครงสร้างทรี (Tree) ทรีเป็นโครงสร้างขอ้ มูลท่ีมีลักษณะของโครงสรา้ งแบบต้นไม้ในธรรมชาติ แต่แตกต่างกันตรงที่ ในธรรมชาตินั้น ต้นไม้จะยนื ต้นขึ้นสูงมรี ากท่ีช้ีลงตรงข้าม แตโ่ ครงสร้างทรีจะกลับด้านโดยกาหนดสว่ น รากไว้ด้านบน และโครงสร้างของตน้ ชด้ี ้านตรงกันขา้ มแทน (a) โครงสรา้ งตน้ ไมใ้ นธรรมชาติ (b) โครงสร้างทรีในคอมพวิ เตอร์ ภาพท่ี 5.1 เปรยี บเทยี บโครงสร้างทรกี บั โครงสร้างตน้ ไม้ในธรรมชาติ โครงสร้างข้อมูลแบบทรีมีลักษณะสาคัญ (วิวัฒน์ อภิสิทธิ์ภิญโญ และอมร มุสิกสาร, 2550 : 180) ดังน้ี 1. ทรีมีโครงสร้างข้อมูลเป็นรูปเชิงระดับ (Hierarchical Structure) มีลักษณะ ของข้อมลู ทกี่ าหนดการแบง่ เกบ็ ข้อมูลเป็นชน้ั ๆ ซึ่งเรยี กว่าระดับ (level) 2. ทรีมีโครงสร้างข้อมูลไม่ตายตัว (Dynamic Structure) ลักษณ ะของ โครงสรา้ งทรีนนั้ สามารถท่ีจะเพม่ิ หรอื ลดข้อมลู ที่จดั เกบ็ ในโครงสรา้ งไดต้ ลอดการทางาน 3. โครงสร้างทรีสามารถน้าข้อมูลเข้าและออกได้ (Insertion and deletation) เน่อื งจากมีโครงสรา้ งท่ไี มต่ ายตัวจึงสามารถดาเนนิ การนาข้อมูลเขา้ และออกได้ตลอดเวลา 4. โครงสร้างทรีเข้าถึงข้อมูลแบบล้าดับ (Ordered Traversal) การเข้าถึงข้อมูล จะตอ้ งเข้าถึงขอ้ มลู ตามลาดบั เชน่ เรม่ิ จากรทู โหนดไลม่ ายังโหนดด้านลา่ งซ้ายไปจนถงึ บนขวา เป็นต้น เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมลู และอัลกอริทึม

57 5.2 ชนดิ ของทรี โครงสร้างทรีเป็นพื้นฐานของการแทนที่ข้อมูลท่ีมีท้ังระดับและความสัมพันธ์ระหว่างโหนด ต่างๆ การนาโครงสร้างทรีมาใช้ในระบบคอมพิวเตอร์ สามารถที่จะระบุชนิดของทรีแยกออกเป็น 2 ชนิด คือ 5.2.1 ทรีท่ัวไป (General Tree) ทรีทั่วไปมีโครงสร้างการเก็บข้อมูล ซ่ึงเรียกว่า โหนด (Node) และเรียกเส้นเช่ือมต่อว่า บรานซ์ (Branch) หรือสาขา โดยจานวนของเส้นบรานซ์จะบอกให้ทราบว่าในโครงสร้างทรีนั้นมี จานวนดีกรีหรือจานวนโหนดลกู ของโหนดน้ันๆ เป็นจานวนเท่าใด โดยมีการเก็บแบบลาดับขั้นเริ่มต้น จากระดับท่ี 0 (Level 0) หรือเรียกว่า โหนดราก (Root node) เชื่อมโยงไปยังโหนดอ่ืนๆ ในระดับที่ 1 (Level 1) และเชื่อมโยงไปยังโหนดอื่นๆ ในระดับถัดลงไป จนถึงระดับสุดท้าย เรียกว่า โหนดใบ (Leaf node) ดงั ภาพที่ 5.2 Level 0 A Level 1 B CD Level 2 E F G HI A Subtree Subtree B C D EFG H I ภาพที่ 5.2 โครงสรา้ งทรี จากภาพท่ี 5.2 เป็นโครงสร้างตัวอย่างของทรีโดยท่ัวไปจะมีการกาหนดให้โหนดตัวแรกเป็น โหนดหลัก เรียกโหนดน้ีว่า รูท (root) ซ่ึงมีจานวนเส้นบรานซ์กระจายออกไป 3 เส้น ทาให้ทราบว่ามี โหนดอีก 3 โหนด หรือ รูท A มีจานวนดีกรี 3 ดีกรี คือ B, C, D โหนด B มีดีกรี 3 ดีกรี คือ E,F,G โหนด C ไม่มีดีกรี ส่วนโหนด D มี 2 ดีกรี คอื H,I หากนบั จานวนของเส้นบรานซ์ และจานวนโหนดจะ ไดจ้ านวนเทา่ กันคือ 8 นน่ั คอื ทาให้ทราบวา่ โครงสรา้ งทรมี ีจ้านวนเส้นบรานซ์ = จา้ นวนโหนด เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมูลและอัลกอรทิ ึม

58 เนื่องจากโครงสร้างข้อมูลท่ีประกอบไปด้วยโหนดหลักพร้อมด้วยโหนดต่างๆ ท่ีถูกจัดเก็บอยู่ ในโครงสร้างข้อมูลเชิงระดับ จึงมีคาศัพท์ที่ใช้ในการเรียกตาแหน่งหรือส่วนประกอบต่างๆ (วิวัฒน์ อภสิ ทิ ธิภ์ ิญโญ และอมร มุสิกสาร, 2550 : 181) ดงั ตอ่ ไปน้ี ทรีว่าง (Empty Tree) โครงสร้างทรที ีไ่ มม่ ีโหนด คอื จานวนโหนดเทา่ กบั ศนู ย์ รทู โหนด (Root node) โหนดแรกสุดของโครงสร้างทรี ซ่ึงอาจมีจานวนดีกรีหรือ ไมม่ ีก็ได้ ดกี รี (Degree) จานวนโหนดลูกของโหนดนั้นๆ มีเส้นบรานซ์แยกสาขา ออกมา บรานซ์ (Branch) เป็นเส้นเชื่อมโยงระหว่างโหนดที่มีความสัมพันธ์กันทาให้ ทราบว่าเป็นโหนดพ่อแม่หรือโหนดลูก ในบางครั้งอาจ เรยี กว่า Edge, Link โหนดพอ่ แม่ (Parent Node) โหนดที่อยู่ระดับท่ีสูงกว่าโหนดที่ระบุโดยเส้นบรานซ์เชื่อม ความสมั พันธ์ใหร้ ู้ โหนดลกู (Child Node) โหนดท่ีอยู่ระดับต่ากว่าโหนดที่ระบุ โดยมีเส้นบรานซ์ เช่อื มความสมั พันธใ์ ห้รู้ โหนดพ่ีนอ้ ง (Sibling Node) โหนดท่ีมีโหนดพ่อแม่เดียวกนั ซ่ึงจะอยู่ในระดับของโหนด เดียวกัน โหนดบรรพชน (Ancestor) โหนดท่ีเป็นโหนดในบรานซ์เดียวกัน โดยเร่ิมลาดับตั้งแต่ รทู โหนดมาจนถงึ โหนดทร่ี ะบุ โหนดสืบสกลุ (Descendant) โหนดทุกโหนดที่อยู่บนทรีย่อยด้านซ้ายและด้านขวาของ โหนดที่ระบุ โหนดใบ (Leaf Node) เป็นโหนดทมี่ ีโหนดลูกหรอื มีคา่ ดกี รเี ทา่ กับศนู ย์ ระดับ (Level) ช้นั ของโหนดซ่ึงระบุด้วยหมายเลข โดยกาหนดให้รทู โหนด เป็นระดับศูนย์และไล่ระดับของโหนดด้วยการเพิ่มจานวน ทีละ 1 ความสงู หรอื ความลึก (Height) ค่าสูงสุดของโหนดในสาขาของทรี กรณีที่โหนดเป็นโหนด ว่างค่าความลึก จะมีค่าเป็น -1 แต่หากไม่ใช่ ค่าความลึก ของโหนดคอื คา่ ระดับสงู สดุ +1 ทรยี อ่ ย (Subtree) โหนดที่เชื่อมโยงซ่ึงถือว่าทรีย่อยเป็นเสมือนกับทรี โดยทรี ย่อยน้ันจะมีทั้งทรียอ่ ยดา้ นซ้ายและทรียอ่ ยด้านขวา เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมูลและอัลกอริทึม

59 ตัวอย่างท่ี 5.1 จากภาพต่อไปนี้สามารถทจ่ี ะระบุถึงตาแหน่งต่างๆ ตามการเรยี กไดด้ งั น้ี A B CD EFG H I รูทโหนด คือ โหนด A ดีกรีของโหนด A คือ 3 บรานซ์ คือ AB, AC, … , DI โหนดพ่อแม่ คอื A, B, F โหนดลกู คือ B, E, F, C, D, G, H, I โหนดพนี่ อ้ ง คอื {B,E,F}, {C,D}, {G,H,I} โหนดบรรพชนของโหนด C คอื A โหนดสืบสกลุ ของโหนด A คอื B, E, F, C, D, G, H, I โหนดใบ คือ C, D, E, G, H, I ระดบั 0 คอื A ระดับ 1 คือ B, E, F ระดับ 2 คือ C, D, G, H, I ความลกึ ของทรี คอื 3 5.2.2 ไบนารที รี (Binary Tree) เปน็ ทรที มี่ โี ครงสร้างเหมอื นทรีท่วั ไป แตล่ กั ษณะเดน่ ของโครงสรา้ งนค้ี อื (1) โหนดของทรีเป็น 0 หรือไมม่ โี หนดที่เรยี กวา่ Empty tree (2) โหนดแตล่ ะโหนดสามารถมีโหนดยอ่ ย (subtree) ได้ไมเ่ กิน 2 โหนด (3) กาหนดเรียกชื่อทรีย่อยด้านซ้ายว่า left subtree และทรีย่อยด้านขวาว่า right subtree A BD EG HI ทรีย่อยดา้ นซ้าย ทรีย่อยด้านขวา ภาพที่ 5.3 โครงสรา้ งไบนารีทรี เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มูลและอลั กอริทมึ

60 จากภาพท่ี 5.3 แสดงโครงสร้างไบนารีทรี ท่ีมีทั้งทรีย่อยด้านซ้ายและทรีย่อยด้านขวาใน โครงสรา้ งไบนารีนั้น ไม่จาเป็นเสมอไปท่ีจะต้องมีโครงสร้างในรูปแบบน้ี บางคร้ังอาจมีเฉพาะด้านซ้าย หรือดา้ นขวา หรอื ไม่มเี ลย ดงั ภาพที่ 5.4 A AA A B BB C (b) (a) (c) (d) A A AA B CB C BC DE D ED E (e) (f) (g) (h) ภาพที่ 5.4 โครงสร้างไบนารีทรแี บบตา่ งๆ ไบนารที รแี บบสมบูรณ์ ไบนารีทรีแบบสมบูรณ์จะกาหนดให้โหนดทุกโหนดต้องมีโหนดลูก 2 โหนด ยกเว้นโหนดใบ และระดับโหนดใบจะต้องอย่ใู นระดับเดยี วกัน A AA BC B C D EF G (a) (b) (c) ภาพที่ 5.5 ไบนารีทรีแบบสมบรู ณ์ สาหรับไบนารีทรีแบบสมบูรณ์สามารถคานวณหาจานวนโหนดได้จากสูตร Nmax = 2n -1 โดย เมือ่ จัดเรยี งตามระดับก็จะได้จานวนเท่ากับการหาค่า แต่ถา้ หากมกี ารคานวณแลว้ จานวนโหนดไม่เต็ม เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มลู และอัลกอริทมึ

61 ระดับที่กาหนดไว้ จะถือว่าไบนารที รีนั้นเป็นไบนารีทรีที่เกือบสมบรู ณ์ โดยโหนดเหล่าน้ันจะไปปรากฏ ในตาแหนง่ ด้านซา้ ยของระดับสดุ ทา้ ยดงั ภาพที่ 5.6 A AA BC B BC D D E D EF (a) (b) (c) ภาพที่ 5.6 ไบนารีทรีแบบเกือบสมบูรณ์ 5.3 การเขา้ ถงึ ขอ้ มลู ในไบนารที รี (Binary Tree Traversal) การเข้าถึงข้อมูลหรือการท่องเข้าไปในไบนารีทรีก็เพื่อที่จะเข้าไปดาเนินการกับข้อมูลที่เก็บไว้ ในโหนดต่างๆ ซึ่งลักษณะของการเข้าไปยังแต่ละโหนดนั้น เหมือนกับการเย่ียม (visit) โหนดต่างๆ เพียง 1 คร้งั ในรูปแบบเชงิ เสน้ วธิ กี ารเข้าเย่ยี มโหนดมี 3 รูปแบบดงั นี้ 1. การเข้าถงึ แบบพรีออร์เดอร์ (Preorder Traversal) 2. การเข้าถึงแบบอนิ ออร์เดอร์ (Inorder Traversal) 3. การเข้าถงึ แบบโพสตอ์ อร์เดอร์ (Postorder Traversal) โดยการเขา้ ถึงแต่ละรูปแบบจะมสี ่วนประกอบที่เก่ยี วขอ้ งดังต่อไปน้ี 1. รูทโหนด (Root node) เป็นโหนดเริม่ ต้นของโครงสรา้ ง แทนสัญลักษณ์ N 2. ทรีย่อยด้านซ้าย (Left Subnode) เป็นทรีย่อยด้านซ้ายของรูทโหนด แทน สัญลักษณ์ L 3. ทรีย่อยด้านขวา (Right Subnode) เป็นทรีย่อยด้านขวาของรูทโหนด แทน สัญลกั ษณ์ R N LR ภาพที่ 5.7 ระบสุ ัญลักษณแ์ ทนค่าตาแหนง่ ของไบนารที รี 5.3.1 การเขา้ แบบพรีออรเ์ ดอร์ (Preorder Traversal) การเข้าถงึ แบบพรอี อร์เดอร์จะใชก้ ารเขา้ ถึงแบบ NLR คือ 1. เขา้ เย่ยี มรทู โหนด (N) เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มูลและอัลกอริทมึ

62 2. เดินทางเข้าเย่ียมดา้ นซา้ ย (L) ของพรอี อรเ์ ดอร์ 3. เดินทางเข้าเย่ยี มดา้ นขวา (R) ของพรีออรเ์ ดอร์ 1 23 ภาพท่ี 5.8 การเข้าถึงแบบพรีออร์เดอร์ การเข้าถงึ แบบพรีออรเ์ ดอร์จะเร่ิมต้นจากจุดแรกคอื รูทโหนด จากน้ันจึงเข้าไปยงั ทรี ย่อยด้านซ้ายและเข้าถงึ ทรยี ่อยดา้ นขวา 5.3.2 การเขา้ ถึงแบบอินออเดอร์ (Inorder Traversal) การเข้าถงึ แบบอนิ ออเดอร์จะใช้การเข้าแบบ LNR ดังน้ี 1. เดินทางเขา้ เยย่ี มด้านซ้าย (L) ของอินออเดอร์ 2. เขา้ เยี่ยมรูทโหนด (N) 3. เดนิ ทางเขา้ เยี่ยมดา้ นขวา (R) ของอินออเดอร์ 2 13 ภาพที่ 5.9 การเข้าถึงแบบอินออเดอร์ การเข้าถึงแบบอินออเดอร์จะดาเนินการเข้าเย่ียมที่ทรีย่อยด้ายซ้ายก่อน จากนั้นจึง ดาเนนิ การท่ีรูทโหนด และส้ินสุดการเขา้ เยี่ยมท่ที รยี ่อยด้านขวา 5.3.3 การเข้าถึงแบบโพสตอ์ อเดอร์ (Postorder Traversal) การเขา้ ถงึ แบบโพสต์ออเดอร์จะใชก้ ารเข้าแบบ LRN ดังน้ี 1. เดนิ ทางเขา้ เยี่ยมทรยี อ่ ยดา้ นซ้าย (L) ของโพสตอ์ อเดอร์ 2. เดินทางเขา้ เย่ียมทรีย่อยด้านขวา (R) ของโพสต์ออเดอร์ 3. เข้าเยี่ยมรูทโหนด (N) 3 12 ภาพท่ี 5.10 การเขา้ ถึงแบบโพสตอ์ อเดอร์ เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมลู และอัลกอริทมึ

63 การเข้าถึงแบบโพสต์ออเดอร์ จะเร่ิมต้นที่ทรีย่อยด้านซ้ายจากน้ันมาประมวลผลต่อ ทท่ี รยี ่อยด้านขวาและส้ินสดุ การประมวลผลที่รทู โหนด ตัวอย่างท่ี 5.2 จงแสดงการเข้าถึงแบบพรีออร์เดอร์ (NLR) โดยกาหนดไบนารีทรีที่ประกอบไปด้วย โหนดตา่ งๆ ดงั ต่อไปนี้ AAA BC BC BC D EF G D EF G D EF G A ครัง้ ท่ี 1 คร้งั ท่ี 2 A A BC BC BC D EF G D EF G D EF G คร้ังท่ี 3 A ครัง้ ท่ี 4 A ครัง้ ท่ี 5 BC BC D EF G D EF G คร้งั ท่ี 6 คร้ังท่ี 7 จากตัวอย่างที่ 5.2 เป็นลาดับข้ันตอนของการดาเนินการซึ่งถือเป็นการดาเนินการ เดินทางตามลาดับของ NRL และหากมีการเข้าเย่ียมและให้ระบุผลลัพธ์ของข้อมูลในโหนดก็จะได้ ข้อมูลเปน็ ABCDEF เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มลู และอัลกอริทมึ

64 ตัวอย่างที่ 5.3 จงแสดงการเข้าถึงแบบอินออเดอร์ (LNR) โดยกาหนดไบนารีทรีท่ีประกอบไปด้วย โหนดต่างๆ ดังตอ่ ไปนี้ A AA BC BC BC D EF G D EF G D EF G A ครั้งที่ 1 ครั้งที่ 2 A A BC BC BC D EF G D EF G D EF G ครง้ั ท่ี 3 คร้งั ที่ 4 คร้งั ที่ 5 AA BC BC D EF G D EF G ครั้งที่ 6 ครง้ั ท่ี 7 จากตัวอย่างที่ 5.3 เป็นลาดับขั้นตอนของการดาเนินการซึ่งถือเป็นการดาเนินการ เดินทางตามลาดับของ LNR และหากมีการเข้าเยี่ยมและให้ระบุผลลัพธ์ของข้อมูลในโหนดก็จะได้ ข้อมูลเปน็ DBEAFCG เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมลู และอัลกอรทิ ึม

65 ตัวอยา่ งที่ 5.4 จงแสดงการเขา้ ถึงแบบโพสต์ออเดอร์ (LRN) โดยกาหนดไบนารที รีท่ีประกอบไปด้วย โหนดต่างๆ ดังตอ่ ไปนี้ A AA BC BC BC D EF G D EF G D EF G A คร้ังท่ี 1 ครง้ั ที่ 2 A A BC BC BC D EF G D EF G D EF G ครง้ั ที่ 3 A ครัง้ ท่ี 4 A ครง้ั ท่ี 5 BC BC D EF G D EF G คร้งั ที่ 6 ครง้ั ท่ี 7 จากตัวอย่างท่ี 5.4 เป็นลาดับข้ันตอนของการดาเนินการซ่ึงถือเป็นการดาเนินการ เดินทางตามลาดับของ LRN และหากมีการเข้าเยี่ยมและให้ระบุผลลัพธ์ของข้อมูลในโหนดก็จะได้ ขอ้ มลู เปน็ DEBFGCA เอกสารประกอบการสอนรายวชิ าโครงสร้างขอ้ มูลและอลั กอรทิ ึม

66 5.4 ทรีกับการด้าเนินการดา้ นนิพจน์ (Expression Tree) การทางานของไบนารีทรีอีกรูปแบบหนึ่งคือ การนาลักษณะของโครงสรา้ งและการท่องเขา้ ไป ในทรีไปใช้งานในด้านนิพจน์ ซงึ่ การดาเนนิ การนี้จะมลี กั ษณะเช่นเดียวกันกับการดาเนนิ การด้านนิพจน์ ของสแตก โดยประกอบไปดว้ ยเคร่ืองหมายดาเนนิ การ (Operator) และตวั ถกู ดาเนินการ (Operand) เครื่องหมายดาเนินการ คือ เครื่องหมายทางการคานวณทางด้านคณิตศาสตร์พ้ืนฐาน 5 ตัว คือ + - * / ^ ตวั ถูกดาเนินการ คือ ตัวแปรหรือตัวเลข เพื่อการคานวณ เมื่อต้องการหาค่าข้อมูลด้วยการใช้ รปู แบบของไบนารีทรี จะต้องมีการกาหนดลกั ษณะดังต่อไปน้ี 1. กาหนดโหนดใบเป็นโหนดที่ใช้ในการเก็บตัวถูกดาเนินการ (Leaf node = Operand) 2. กาหนดรูทโหนดและโหนดลูกเป็นโหนดเก็บตัวถูกดาเนินการ (root node + parent node = Operator) 3. กาหนดทรียอ่ ยเปน็ นิพจนข์ องการดาเนนิ การหลัก (Subtree = Operator) ลักษณะการเข้าถึงในแบบต่างๆ ของทรี ไม่ว่าจะเป็น infix, postfix และ prefix เช่น การ เข้าถึงแบบอินออเดอร์เป็นต้นแบบของนิพจน์ infix การเข้าถึงแบบโพสออเดอร์ เป็นต้นแบบของ นพิ จน์ postfix และการเขา้ ถงึ แบบพรีออเดอรเ์ ปน็ ต้นแบบของนิพจน์ prefix + AB ภาพท่ี 5.11 รูปแบบนิพจน์ทรีในการดาเนินการ (a-b) จากภาพที่ 5.11 หากนามาเขียนในลักษณะของการเข้าถึงข้อมูลแบบทรีสามารถแสดงได้ดัง ตารางที่ 5.1 เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมลู และอลั กอรทิ มึ

67 ตารางที่ 5.1 ลกั ษณะของการเขา้ ถงึ ข้อมูลแบบทรี รปู แบบการเขา้ ถึง นพิ จนท์ รี เปรียบเทียบกับนพิ จน์ รปู ภาพ พรอี อเดอร์ (preorder) +AB Prefix 1 A อินออเดอร์ (inorder) A+B Infix 23 BC 2 A โพสออเดอร์ (postorder) AB+ Postfix 13 BC 3 A 12 BC ตัวอยา่ งท่ี 5.5 จากนพิ จน์ a*b/3+c-(d^4)+e*f สามารถเขยี นในแบบรูปภาพของไบนารีทรดี ังนี้ - /+ * + ^* a b3 c d 4e f นิพจนพ์ รีออเดอร์ (Preorder) : -/*ab+3c+^d4*ef นพิ จนอ์ นิ ออเดอร์ (Inorder) : a*b/3+c-d^4+c*f นิพจน์โพสตอ์ อเดอร์ (Postorder) : ab*3c+/d4^ef*+- เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มลู และอลั กอริทมึ

68 5.5 การแทนโครงสร้างไบนารีทรแี บบซเี ควนเชยี ล (Sequential Representation) การแทนโครงสร้างไบนารีทรีแบบซีเควนเชียลเป็นการแทนในแบบอาร์เรย์ แตจ่ ะมีการทางาน ได้ดกี ็ตอ่ เม่ือโครงสรา้ งไบนารีทรีเป็นโครงสรา้ งทส่ี มบูรณ์ 1 A 23 BC 4 56 7 D EF G ภาพท่ี 5.12 โครงสรา้ งไบนารที รพี รอ้ มหมายเลขโหนด จากภาพที่ 5.12 เป็นโครงสร้างไบนารีทรีแบบสมบูรณ์ มีการระบุหมายเลขให้กับโหนด โดย การกาหนดหมายเลขตอ้ งเร่ิมตั้งแตร่ ูทโหนด กาหนดเป็นลาดบั ท่ี 1 ไล่โหนดจากซา้ ยไปขวาจนถงึ โหนด ใบในลาดับสุดท้าย แต่ในลักษณะที่ไม่ใช่ไบนารีทรีแบบสมบูรณ์ก็จะต้องต่อเติมส่วนที่ขาดหายไปให้ สมบรู ณ์ ดงั ภาพที่ 5.13 1 A 23 BC 4 56 7 DE FG 8 9 10 11 12 13 14 15 H I J KL M ภาพท่ี 5.13 การต่อเติมโหนดใหไ้ บนารีทรเี พื่อให้ทรีสมบูรณ์ เมื่อได้ไบนารีทรีที่สมบูรณ์ก็สามารถแทนโครงสร้างแบบซีเควนเชียลได้ โดยกาหนดจานวน ช่องของอารเ์ รย์ตามจานวนของหมายเลขโหนด ดงั ภาพท่ี 5.15 เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มูลและอัลกอรทิ ึม

69 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] AABCDEFGH I J K L M ภาพท่ี 5.14 การแทนโครงสรา้ งไบนารที รีแบบซีเควนเชียล จากภาพท่ี 5.14 แทนดว้ ยโครงสรา้ งแบบซีเควนเชยี ลหรืออารเ์ รย์ 1 มิติ จานวน 15 ช่อง โดย บรรจุขอ้ มูลลงตามหมายเลขของชอ่ ง ชอ่ งที่ไม่มีข้อมูลจะเว้นวา่ งไว้ แต่โดยปกติการกาหนดจานวนช่อง ของอาร์เรยน์ ้ันสามารถคานวณหาค่าได้ การหาความสัมพันธข์ องโหนด สามารถคานวณหาได้ดังตาราง ที่ 5.2 ตารางท่ี 5.2 การหาความสัมพนั ธ์ของโหนดจากโครงสร้างซเี ควนเชยี ล การคน้ หา สูตร กา้ หนดคา่ โหนดด้านซา้ ยของ A[i] A[2i] 2i ≤ n โหนดดา้ นขวาของ A[i] A[2i+1] 2i+1 ≤ n โหนดพอ่ แม่ของ A[i] A[i div 2] A[1] i>n รูดโหนด ถา้ ใช่ A ไม่ใช่อารเ์ รยว์ ่าง ตรวจสอบ A[i] เปน็ โหนดใบ 2i > n ตวั อย่างท่ี 5.6 จากภาพจงตอบคาถามตอ่ ไปน้ี [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] AABCDEFGH I J K L M 1. โหนดลกู ดา้ นขวาของ A[5] พรอ้ มคา่ ข้อมูล จากสูตร A[2i+1] โดยท่ี 2i+1  n; i=5; n=13 แทนค่า A[2(5) + 1] = A[11] 2i + 1 = 11  13  โหนดลกู ด้านขวาของ A[5] คือ A[11] คา่ ของข้อมลู คือ K 2. โหนดพ่อแม่ของโหนด G คือโหนดใด สตู ร A[i div 2] โดยที่ i>1 สาหรับโจทย์น้เี นอ่ื งจาก G ถูกจัดเกบ็ ในตาแหนง่ A[7] ดังนั้น i =7 แทนคา่ A[7 div 2] = 3 7 div 2 = 3 > 1  โหนดพอ่ แม่ของ G คือ A[3] คา่ ของขอ้ มูลคอื C 3. รูทโหนดคือ เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มูลและอัลกอรทิ มึ

70 สูตร A[1] โดยทอี่ ารเ์ รย์ไมใ่ ชอ่ าร์เรย์ว่าง A[1] = A  รทู โหนด คอื A 4. โหนดใบของอาร์เรยช์ ุดนี้ สตู ร 2i > n (อาร์เรย์ช่องใดคูณด้วย 2 แลว้ มคี า่ มากกวา่ N เม่ือ N=13) โดยจะต้องตดั คา่ i = 1 ออกเนื่องจากเปน็ รทู โหนด i 2 * i i > x ค่าขอ้ มลู 2 4- 3 6- 4 8- 5 10  -  6 12  - 7 14 G 8 16  H 9 18  I 10 20 J 11 22  K   12 24  L 13 26 M  อาร์เรย์ท่ีเป็นโหนดใบ คือ A[7], A[8], A[9], A[10], A[11], A[12] และ A[13] ค่าข้อมูล G, H, I, J, k, L, M ตามลาดบั 5.6 การแปลงทรีเปน็ ไบนารที รี เน่ืองจากโครงสร้างของทรีท่ัวไปมีลักษณะของโหนดลูกท่ีมากกว่า 2 และการจัดการได้ยาก กว่าไบนารีทรีท่ีมีการกาหนดโหนดลูกไม่เกิน 2 มีวิธีการปรับเปล่ียนโครงสร้างเพื่อให้ทรีทั่วไป เปลีย่ นเป็นไบนารที รคี อื 1. สาหรบั โหนดลูกทเี่ ปน็ โหนดแรกให้ปรับเปลี่ยนเปน็ ทรีย่อยด้านซ้าย 2. จากนัน้ หากโหนดมีพีน่ อ้ งไมว่ ่าจะมจี านวนเท่าใดใหเ้ ปลีย่ นเป็นทรีย่อยดา้ นขวาทุกตวั เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มลู และอัลกอริทึม

71 ตัวอย่างท่ี 5.7 จงเปล่ียนทรที ั่วไปให้เปน็ ไบนารีทรี A B CD EFG HI จากรูปพิจารณามีโหนดลูกท่ีเป็นโหนดแรกอยู่ 3 โหนดคือ B,C,G ซ่ึงเป็นโหนดลูกของ A,B,F ตามลาดบั โหนดเหลา่ นี้จะถกู จัดเป็นทรียอ่ ยดา้ นซ้าย ส่วนโหนด B มพี น่ี อ้ งคอื E,F โหนดเหล่าน้ีจะถกู จดั เปน็ โหนดย่อยด้านขวาของโหนด B ส่วนโหนด C มีพ่นี ้องคือ D โหนดเหลา่ น้จี ะถูกจดั เป็นโหนดย่อยด้านขวาของโหนด C สว่ นโหนด G มีพนี่ อ้ งคอื H,I โหนดเหล่านี้จะถูกจดั เป็นโหนดย่อยด้านขวาของโหนด G A B CD EFG HI ลบเส้นบรานซเ์ ดิมออกจะเหลอื เฉพาะเส้นของการเชื่อมโยงใหม่ A B CD EFG HI เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมลู และอลั กอรทิ มึ

72 จากน้นั ปรบั โครงสรา้ งให้แสดงตามแบบไบนารีทรีกเ็ ปน็ อันเสร็จสมบูรณ์ A B EC FD GHI เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมูลและอัลกอรทิ ึม

73 ชอ่ื หน่วยเรียน : กราฟ (Graph) รหสั วชิ า 13-132-207 หนว่ ยเรียนที่ 6 เวลาสอน 3 คาบ ชื่อบทเรยี น 6.1 ความหมายและลักษณะของกราฟ 6.2 ประเภทของกราฟ 6.3 การแทนขอ้ มูลกราฟ 6.4 การดาเนินการบนกราฟ 6.5 การท่องไปในกราฟ จดุ ประสงคก์ ารสอน 6.1 รู้ความหมายและลักษณะของกราฟ 6.1.1 บอกความหมายของกราฟ 6.1.2 บอกลกั ษณะของกราฟ 6.2 เขา้ ใจประเภทของกราฟ 6.2.1 อธบิ ายและยกตัวอย่างกราฟมีทิศทาง 6.2.2 อธิบายและยกตวั อยา่ งกราฟไม่มีทศิ ทาง 6.2.3 อธิบายและยกตวั อย่างกราฟมีน้าหนัก 6.2.4 อธิบายและยกตัวอย่างกราฟไม่มีน้าหนัก 6.3 แกป้ ญั หาการแทนขอ้ มูลกราฟ 6.3.1 หาผลลพั ธ์การแทนข้อมลู กราฟด้วยอาร์เรยแ์ ละเมทรกิ ซ์ 6.3.2 หาผลลพั ธ์การแทนข้อมูลกราฟดว้ ยลงิ ค์ลสิ ต์ 6.3.3 หาผลลัพธ์จานวนเสน้ ทางระหว่างโหนด 6.4 แกป้ ญั หาการดาเนินการบนกราฟ 6.4.1 หาผลลัพธ์การเพ่มิ บนกราฟ 6.4.2 หาผลลัพธ์การลบบนกราฟ 6.5 สรา้ งการท่องไปในกราฟ 6.5.1 หาผลลัพธ์การทอ่ งแบบแนวกวา้ ง 6.5.2 หาผลลพั ธ์การทอ่ งแบบแนวลึก เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมลู และอลั กอริทึม

74 หน่วยเรยี นท่ี 6 กราฟ (Graph) กราฟเป็นโครงสร้างข้อมลู ทเ่ี ช่ือมความสมั พันธร์ ะหว่างโหนด (Vertex) โดยผ่านทางเส้นเชื่อม (Edge) ซ่ึงกราฟเป็นโครงสร้างข้อมูลที่มีการนาไปใช้ในงานท่ีเกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้าง ซบั ซ้อน เช่น การวางขา่ ยงานคอมพวิ เตอร์ การวิเคราะหเ์ ส้นทางวิกฤติ 6.1 ความหมายและลกั ษณะของกราฟ 6.1.1 ความหมายของกราฟ นกั วชิ าการไดใ้ ห้ความหมายของคาว่า “กราฟ” ไว้หลายความหมาย ดังน้ี ขนิษฐา นามี (2548 : 315) ได้ให้ความหมายของกราฟไว้ว่า กราฟ หมายถึง กลุ่มของโหนด หลาย ๆ โหนดมาเช่ือมต่อกันระหว่างคู่โหนดด้วยเส้นเชื่อม โดยเรียกโหนดน้ันว่า Vertices ส่วนของ เสน้ เชอ่ื มที่มาเช่ือมตอ่ กนั ระหวา่ งคูโ่ หนดใด ๆ เรยี กว่า Arcs หรอื Edges โอภาส เอย่ี มสิริวงศ์ (2549 : 265) ไดใ้ ห้ความหมายของกราฟไว้วา่ กราฟ หมายถงึ กลุ่มของ โหนดท่ีเรียกวา่ เวอรเ์ ท็กซ์ (Vertex/Vertices) และกลุ่มของเอดจ์ (Edges) ที่ใช้เช่ือมโยงระหว่างเวอร์ เทกซ์ หรอื อาจกล่าวอีกนัยหน่ึงว่า กราฟกค็ ือกลุ่มของเซต ซึง่ ประกอบดว้ ยกลุ่มเซตของเวอรเ์ ท็กซ์และ เซตของเอดจ์ บุญสบื โพธ์ศิ รี, รุ่งอรณุ ประจักจติ ร์ และ สมเจตต์ ภญิ ญาคง (2551 : 123) ได้ให้ความหมาย ของกราฟไว้วา่ กราฟ หมายถึง เซ็ตของจดุ และเซต็ ของเสน้ ซ่ึงเส้นจะเปน็ ตวั เชอ่ื มจากจุดหนงึ่ ไปยังอีก จดุ หนง่ึ โดยเรยี กวา่ โหนดของกราฟ หรอื เรยี กโหนด (Vertices) และการเชอ่ื มต่อวา่ Edge กชกร ณ นครพนม และคณะ (2556 : 11-5) ได้ให้ความหมายของกราฟไว้ว่า กราฟ หมายถึง โครงสร้างข้อมูลท่ีใช้เพ่ือแสดงความสัมพันธ์ระหว่างวัตถุ โดยแทนวัตถุด้วยโหนด (Node) ของกราฟ หรือจุด (Vertex) และเชื่อมโยงความสัมพันธ์จากโหนดหน่ึงไปยังอีกโหนดหน่ึงด้วยเส้นหรือเอดจ์ (Edge) กลา่ วโดยสรปุ ได้วา่ กราฟ หมายถงึ กลุ่มของโหนด (Vertices) และกลุ่มของเอดจ์ (Edges) ที่ ใช้เช่อื มโยงความสมั พันธร์ ะหวา่ งโหนดหนึง่ ไปยงั อีกโหนดหนงึ่ 6.1.2 ลกั ษณะของกราฟ กราฟเป็นโครงสร้างข้อมูลทีม่ ีลักษณะ (วุฒิพงษ์ เขอ่ื นดิน, 2553 : 352) ดงั นี้ 1. เป็นโครงสร้างข้อมูลท้ัง 2 แบบ คือ แบบเป็นเชิงเส้น (Linear Structure) และ แบบไม่เป็นเชิงเส้น (Non Linear Structure) คือ เขยี นโปรแกรมได้ท้งั ใชอ้ าร์เรย์ และพอยน์เตอร์ 2. เป็นโครงสร้างข้อมูลเชิงตาข่าย (Network Structure) เน่ืองจากมีลักษณะ การเชอื่ มต่อระหวา่ งเวอรเ์ ทกซ์ได้หลากหลาย ทาใหม้ ลี กั ษณะเหมือนตาข่าย 3. เป็นโครงสร้างแบบไม่ตายตัว (Dynamic Structure) เน่ืองจากกราฟสามารถ เปลี่ยนแปลงโครงสร้างของข้อมลู ได้ได้ดว้ ยการเพ่ิมหรือลบเวอร์เทกซ์ ซึ่งทาให้เกดิ การเปล่ียนแปลงทั้ง เวอร์เท็กซ์และเสน้ เชือ่ มต่อ เอกสารประกอบการสอนรายวชิ าโครงสร้างขอ้ มูลและอลั กอริทมึ

75 4. การเข้าถึงแบบล้าดับ (Ordered Traversal) การเข้าถึงเวอร์เท็กซ์ต่าง ๆ โดย จะเริม่ ตน้ จากเวอรเ์ ท็กซแ์ รกและเรยี งตามลาดับไปยังเวอร์เทก็ ซต์ ่อ ๆ ไป ตามเส้นการเชอื่ มตอ่ 6.2 ประเภทของกราฟ ประเภทของโครงสรา้ งข้อมูลแบบกราฟ แบง่ เป็น 4 ประเภท ดังนี้ 6.2.1 กราฟมีทิศทาง (Directed Graph หรือ Digraph) เป็นกราฟที่ระบุทิศทางการ เช่ือมต่อ ซงึ่ เปน็ การบอกทศิ ทางของการเดนิ ทางจากโหนดหน่ึงไปยงั โหนดต่อไป ดังภาพที่ 6.1 AB CD E ภาพท่ี 6.1 กราฟมที ิศทาง โดยกาหนดสมการ G = (V,E) กาหนดให้ G แทน กราฟ V แทน โหนดบนกราฟ E แทน เส้นเชอ่ื มโยงบนกราฟ ดังน้ัน ในการจัดเก็บส่วนความสัมพันธ์เส้นเช่ืองโยง V และ E แล้ว ประสิทธิภาพใน การทางานของขั้นตอนวิธีได้เป็น O (|V|+|E|) เป็นเวลาท่ีใช้ในการเข้าถึงโหนดและเส้นเชื่อมโยงของ กราฟ จากภาพท่ี 6.1 สามารถเขยี นเซตแทนกราฟได้ ดงั นี้ G = {V, E} V = {A, B, C, D, E} E = {(A,B), (A,C), (B,D), (B,E), (C,D), (D,E)} 6.2.2 กราฟไม่มที ิศทาง (Undirected Graph) เป็นกราฟที่ไม่ระบุทิศทางของการเช่ือมต่อ ซึง่ จะทาใหส้ ามารถเดนิ ทางไปมาระหว่างกันได้ ดงั ภาพที่ 6.2 AB CD E ภาพท่ี 6.2 กราฟไม่มีทิศทาง เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมลู และอัลกอริทึม

76 จากภาพท่ี 6.2 สามารถเขยี นเซตแทนกราฟได้ ดงั นี้ G = {V, E} V = {A, B, C, D, E} E = {(A,B), (A,C), (B,D), (B,E), (C,D), (D,E)} 6.2.3 กราฟมีน้าหนัก (Weighted Graph) เป็นกราฟท่ีระบุน้าหนักของเส้นเชื่อม โดยระบุ ตวั เลขแทนระยะทางจากเวอร์เทก็ ซ์หน่ึงไปยงั อกี เวอรเ์ ทก็ ซห์ นงึ่ ดงั ภาพท่ี 6.3 A6 B 7 54 C3 D2 E ภาพท่ี 6.3 กราฟมนี ้าหนัก 6.2.4 กราฟไม่มีน้าหนัก (Unweighted Graph) เป็นกราฟที่ไม่กาหนดน้าหนักของเส้น เช่ือมตอ่ โดยจะใหแ้ ต่ละเส้นมนี า้ หนกั เปน็ 1 เทา่ กันหมดทกุ เสน้ ดังภาพที่ 6.4 A1 B 1 11 C1 D1 E ภาพท่ี 6.4 กราฟไมม่ นี า้ หนัก 6.3 การแทนขอ้ มูลกราฟ 6.3.1 การแทนข้อมูลกราฟด้วยอาร์เรยแ์ ละเมทรกิ ซ์ การแทนข้อมูลกราฟด้วยเมทริกซ์และอารเ์ รย์ แทนความสัมพันธ์น้ันดว้ ย nxn ซึ่ง n คือ A, B, C, D, E เป็นจานวน 5 โหนด ทาให้ได้ค่าเมทริกซ์ จานวน 5x5 = 25 ช่อง และหากพิจารณาตามทิศ ทางการเช่ือมต่อ สามารถพิจารณาไดต้ ามทิศทางต่อไปนี้ 1. การแทนข้อมูลกราฟไม่มีทิศทาง การแทนข้อมูลกราฟแบบไม่มีทิศทาง กาหนดให้สมาชิกของ A เป็นอาร์เรย์ 2 มิติ ท่ี มีขนาด nxn เม่อื n เป็นจานวนโหนดบนกราฟ สามารถเขียนเป็นสมการไดด้ ังนี้ Aij = a(i,j) ; 1 เมอื่ (i,j) และ (j,i) E 0 เมอื่ (i,j) และ (j,i) E เอกสารประกอบการสอนรายวชิ าโครงสร้างขอ้ มลู และอลั กอรทิ มึ

77 ตัวอยา่ งท่ี 6.1 จงแทนข้อมลู กราฟไม่มีทศิ ทาง ด้วยอารเ์ รย์และเมทริกซ์ AB CD E จากภาพสามารถแทนข้อมลู ด้วยอาร์เรย์และเมทรกิ ซ์ได้ ดังภาพท่ี ABCDE A= 0 1 1 0 0 A01100 10011 B10011 10010 C10010 01101 D01101 01010 E01010 (a) การแทนขอ้ มูลด้วยอาร์เรย์ (b) การแทนข้อมลู ด้วยเมทรกิ ซ์ ภาพท่ี 6.5 การแทนข้อมูลกราฟไม่มีทิศทางดว้ ยอาร์เรยแ์ ละเมทริกซ์ จากภาพท่ี 6.5 แทนที่อาร์เรย์และเมทริกซ์ด้วยจานวนโหนด โดยกาหนดโหนด แนวนอนเปน็ โหนดตน้ ทางและแนวต้งั เป็นโหนดปลายทาง สามารถเขยี นลาดับโดยระบคุ ่าได้ดงั น้ี โหนด A มเี ส้นเช่อื มต่อระบไุ ป B,C ระบุหมายเลข 1 นอกนั้นระบคุ ่าเปน็ 0 โหนด B มเี ส้นเชอื่ มต่อระบไุ ป A,D,E ระบุหมายเลข 1 นอกนนั้ ระบคุ า่ เปน็ 0 โหนด C มเี ส้นเชื่อมต่อระบไุ ป A,D ระบหุ มายเลข 1 นอกนั้นระบคุ า่ เปน็ 0 โหนด D มเี สน้ เชอ่ื มต่อระบุไป B,C,E ระบุหมายเลข 1 นอกนน้ั ระบุค่าเป็น 0 โหนด E มเี สน้ เชื่อมต่อระบุไป B,D ระบหุ มายเลข 1 นอกน้ันระบุค่าเปน็ 0 2. การแทนขอ้ มูลกราฟมีทิศทาง การแทนข้อมูลกราฟแบบมีทิศทาง กาหนดให้สมาชิกของ A เป็นอาร์เรย์ 2 มิติ ท่ีมี ขนาด nxn เมือ่ n เป็นจานวนโหนดบนกราฟ สามารถเขยี นเปน็ สมการได้ดังน้ี Aij = a(i,j) ; 1 เม่ือ (i,j) E 0 เมอ่ื (i,j) E เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมูลและอัลกอรทิ มึ

78 ตวั อยา่ งที่ 6.2 จงแทนข้อมูลกราฟมีทิศทาง ด้วยอาร์เรยแ์ ละเมทริกซ์ AB CD E จากภาพสามารถแทนขอ้ มูลด้วยอาร์เรยแ์ ละเมทริกซ์ได้ ดังภาพท่ี ABCDE A= 0 0 1 0 0 A00100 10001 B10001 00010 C00010 01001 D01001 00010 E00010 (a) การแทนขอ้ มูลด้วยอารเ์ รย์ (b) การแทนข้อมูลดว้ ยเมทรกิ ซ์ ภาพที่ 6.6 การแทนข้อมลู กราฟมีทิศทางด้วยอาร์เรยแ์ ละเมทรกิ ซ์ จากภาพท่ี 6.6 แทนที่อาร์เรย์และเมทริกซ์ด้วยจานวนโหนด โดยกาหนดโหนด แนวนอนเป็นโหนดต้นทางและแนวต้งั เปน็ โหนดปลายทาง สามารถเขียนลาดบั โดยระบคุ า่ ไดด้ ังน้ี โหนด A มีเสน้ เช่อื มต่อระบไุ ป C ระบุหมายเลข 1 นอกนนั้ ระบุค่าเป็น 0 โหนด B มเี สน้ เชือ่ มต่อระบุไป A,E ระบุหมายเลข 1 นอกน้ันระบคุ ่าเปน็ 0 โหนด C มีเสน้ เช่อื มต่อระบุไป D ระบุหมายเลข 1 นอกนน้ั ระบุค่าเป็น 0 โหนด D มเี ส้นเชอื่ มตอ่ ระบุไป B,E ระบหุ มายเลข 1 นอกน้ันระบุค่าเปน็ 0 โหนด E มีเสน้ เชื่อมต่อระบุไป D ระบุหมายเลข 1 นอกนัน้ ระบุค่าเปน็ 0 3. การแทนข้อมูลกราฟมีน้าหนักและมีทศิ ทาง การแทนข้อมูลกราฟมีน้าหนักและมีทิศทาง กาหนดให้สมาชิกของ A เป็นอาร์เรย์ 2 มิติ ที่มขี นาด nxn เม่อื n เปน็ จานวนโหนดบนกราฟ สามารถเขยี นเป็นสมการไดด้ งั นี้ Aij = a(i,j) ; Wij เมือ่ (i,j) E Wij เมื่อ (i,j) E 0 กรณีอื่น ๆ เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมูลและอลั กอรทิ ึม

79 ตวั อยา่ งท่ี 6.3 จงแทนข้อมูลกราฟมนี ้าหนักและมีทิศทาง ด้วยอาร์เรย์และเมทริกซ์ A3 B 2 57 จากภาพสามารถแCทนขอ้ ม6ลู ด้วยอDารเ์ รยแ์ 4ละเมทรEิกซ์ได้ ดงั ภาพท่ี 6.7 ABCDE A= 0 3 2 0 0 A03200 00050 B00050 00060 C00060 00004 D00004 07000 E07000 (a) การแทนขอ้ มลู ด้วยอารเ์ รย์ (b) การแทนข้อมลู ดว้ ยเมทรกิ ซ์ ภาพที่ 6.7 การแทนข้อมูลกราฟมีนา้ หนักและมีทศิ ทางด้วยอาร์เรยแ์ ละเมทริกซ์ จากภาพที่ 6.7 สามารถกาหนดโหนด โดยระบุคา่ ไดด้ ังน้ี โหนด A มเี สน้ เชอ่ื มต่อระบุไป B,C ระบุหมายเลข 3,2 นอกน้นั ระบุคา่ เปน็ 0 โหนด B มเี สน้ เช่ือมตอ่ ระบุไป D ระบหุ มายเลข 5 นอกนัน้ ระบคุ ่าเปน็ 0 โหนด C มเี ส้นเช่อื มต่อระบุไป D ระบหุ มายเลข 6 นอกนั้นระบคุ ่าเป็น 0 โหนด D มเี สน้ เช่ือมต่อระบุไป E ระบุหมายเลข 4 นอกนัน้ ระบุค่าเปน็ 0 โหนด E มีเส้นเช่อื มต่อระบุไป B ระบหุ มายเลข 7 นอกนนั้ ระบคุ า่ เปน็ 0 6.3.2 การแทนข้อมูลกราฟด้วยลิงค์ลิสต์ การแทนข้อมูลกราฟด้วยลิงค์ลิสต์เพื่อจัดเก็บค่าของเส้นเชื่อมโยง จะเก็บเฉพาะโหนดที่มี ความสัมพันธก์ ันเท่านน้ั 1. การแทนขอ้ มลู กราฟไม่มีทิศทาง การแทนข้อมูลกราฟไม่มีทิศทางโดยใช้พอยน์เตอร์ (Pointer) ทางซ้ายช้ีตามแนวดิ่ง เพอ่ื เชื่อมโยงแต่ละโหนด และพอยนเ์ ตอร์ทางขวาชตี้ ามแนวนอนเพ่ือเช่ือมโยงไปยังเสน้ เชอื่ มโยงแต่ละ โหนด สามารถแทนลงิ ค์ลิสตไ์ ด้จากโหนดเร่ิมต้นเช่อื มโยงทุกเสน้ ตามจานวนเสน้ ท่ีเชอ่ื มโยงโหนดน้นั ๆ เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมลู และอัลกอรทิ ึม

80 ตวั อยา่ งท่ี 6.4 แทนข้อมูลกราฟไมม่ ีทิศทาง ด้วยลงิ คล์ ิสต์ AB CD E จากภาพสามารถแทนขอ้ มลู ด้วยลงิ ค์ลิสต์ได้ ดงั ภาพที่ 6.8 ABC BADE CAD DBCE EBD ภาพที่ 6.8 การแทนข้อมูลกราฟไม่มีทิศทางด้วยลงิ คล์ สิ ต์ 2. การแทนขอ้ มูลกราฟมีทิศทาง การแทนข้อมลู กราฟมที ิศทางโดยใช้พอยน์เตอร์ (Pointer) ทางซ้ายช้ีตามแนวดิ่งเพ่ือ เชื่อมโยงแต่ละโหนด และพอยนเ์ ตอร์ทางขวาตามแนวนอนเพ่ือเชื่อมโยงไปยังเสน้ เชอ่ื มโยงแตล่ ะโหนด โดยสามารถแทนด้วยลงิ ค์ลิสต์ได้จากโหนดเร่ิมต้นไปตามเสน้ แนวลูกศรชี้เช่ือมโยงจากโหนดหน่ึงไปยัง อีกโหนดหนึ่ง ตัวอยา่ งที่ 6.5 แทนข้อมลู กราฟมีทศิ ทาง ดว้ ยลิงคล์ ิสต์ AB CD E จากภาพสามารถแทนขอ้ มลู ด้วยลงิ คล์ สิ ต์ได้ ดังภาพที่ 6.9 เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมลู และอัลกอรทิ ึม

81 ABC BDE CD DE E ภาพที่ 6.9 การแทนข้อมลู กราฟมีทิศทางดว้ ยลิงคล์ ิสต์ 3. การแทนขอ้ มลู กราฟมีน้าหนกั และมที ิศทาง ตวั อยา่ งท่ี 6.6 แทนข้อมูลกราฟมีทิศทาง ด้วยลงิ คล์ สิ ต์ A1 B 6 25 C3 D4 E จากภาพสามารถแทนข้อมูลด้วยลิงค์ลิสตไ์ ด้ ดังภาพท่ี 6.10 A B1 C6 B D2 C D3 D E4 E B5 ภาพท่ี 6.10 การแทนข้อมลู กราฟมีน้าหนักและมีทิศทางดว้ ยลิงคล์ ิสต์ เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มูลและอัลกอรทิ มึ

82 6.3.3 การคา้ นวณจ้านวนเสน้ ทางระหว่างโหนด การคานวณหาจานวนเส้นทางระหว่างโหนด คือ การหาจานวนเส้นเชอ่ื มต่อจากโหนดตน้ ทาง ไปถึงโหนดปลายทางทกี่ าหนดว่ามีจานวนเท่าใด ตัวอยา่ งท่ี 6.7 จงแทนที่ดว้ ยเมทริกซ์และหาเสน้ ทางท่มี จี านวนเสน้ เช่อื ม 2 เส้น AB CD E จากมีจานวนโหนด 5 โหนด คอื A, B, C, D, E จานวนช่องเมทรกิ ซ์ 5x5 = 25 ช่อง ABCDE A01100 B00010 C00010 D00001 E01000 คานวนหาจานวนเส้นเชื่อมต่อ 2 เส้น 01100 01100 Z11 Z12 Z13 Z14 Z15 00010 00010 Z21 Z22 Z23 Z24 Z25 00010 00010 Z= Z31 Z32 Z33 Z34 Z35 00001 00001 Z41 Z42 Z43 Z44 Z45 01000 01000 Z51 Z52 Z53 Z54 Z55 Z11= 0(0)+ 1(0)+ Z12= 0(1)+ 1(0)+ Z13= 0(1)+ 1(0)+ Z14= 0(0)+ 1(1)+ Z15= 0(0)+1(0)+ 1(0)+0(0)+0(0)=0 1(0)+0(0)+0(1)=0 1(0)+0(0)+0(0)=0 1(1)+0(0)+0(0)=2 1(0)+0(1)+0(0)=0 Z21=0(0)+ 0(0)+ Z22=0(1)+ 0(0)+ Z23=0(1)+ 0(0)+ Z24=0(0)+ 0(1)+ Z25=0(0)+ 0(0)+ 0(0)+1(0)+0(0)=0 0(0)+1(0)+0(1)=0 0(0)+1(0)+0(0)=0 0(1)+1(0)+0(0)=0 0(0)+1(1)+0(0)=1 Z31=0(0)+ 0(0)+ Z32 =0(1)+ 0(0)+ Z33 =0(1)+ 0(0)+ Z34 =0(0)+ 0(1)+ Z35=0(0)+ 0(0)+ 0(0)+1(0)+0(0)=0 0(0)+1(0)+0(1)=0 0(0)+1(0)+0(0)=0 0(1)+1(0)+0(0)=0 0(0)+1(1)+0(0)=1 Z41=0(0)+ 0(0)+ Z42 =0(1)+ 0(0)+ Z43 =0(1)+ 0(0)+ Z44 =0(0)+ 0(1)+ Z45=0(0)+ 0(0)+ 0(0)+0(0)+1(0)=0 0(0)+0(0)+1(1)=1 0(0)+0(0)+1(0)=0 0(1)+0(0)+1(0)=0 0(0)+0(1)+1(0)=0 Z51=0(0)+ 1(0)+ Z52 =0(1)+ 1(0)+ Z53 =0(1)+ 1(0)+ Z54 =0(0)+ 1(1)+ Z55=0(0)+ 1(0)+ 0(0)+0(0)+0(0)=0 0(0)+0(0)+0(1)=0 0(0)+0(0)+0(0)=0 0(1)+0(0)+0(0)=1 0(0)+0(1)+0(0)=0 เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มลู และอัลกอริทึม

83 ABCDE A00020 B00001 C00001 D01000 E00010 เสน้ ทางเชอื่ มต่อ 2 เสน้ จาก A ไป D มี 2 เสน้ ทาง คือ ABD และ ACD เส้นทางเชือ่ มต่อ 2 เสน้ จาก B ไป E มี 1 เส้นทาง คือ BDE เส้นทางเชื่อมต่อ 2 เสน้ จาก C ไป E มี 1 เสน้ ทาง คือ CDE เสน้ ทางเชอื่ มต่อ 2 เส้นจาก D ไป B มี 1 เส้นทาง คือ DEB เสน้ ทางเชอ่ื มต่อ 2 เสน้ จาก E ไป D มี 1 เสน้ ทาง คอื EBD ตวั อยา่ งที่ 6.8 จงแทนท่ดี ้วยเมทรกิ ซ์และหาเสน้ ทางทมี่ ีจานวนเส้นเชื่อม 2 เสน้ และ 3 เส้น AB CD E จากมจี านวนโหนด 5 โหนด คอื A, B, C, D, E จานวนชอ่ งเมทริกซ์ 5x5 = 25 ชอ่ ง ABCDE A01100 B10011 C10010 D01101 E01010 คา้ นวนหาจา้ นวนเส้นเชอื่ มต่อ 2 เส้น ABCDE 01100 01100 A20021 10011 10011 B03211 10010 10010 = C 0 2 2 0 1 01101 01101 D2103 1 01010 01010 E11112 เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมลู และอลั กอรทิ ึม

84 เส้นทางเชื่อมต่อ 2 เสน้ จาก A ไป A มี 2 เส้นทาง คอื ABA และ ACA เส้นทางเชอ่ื มต่อ 2 เสน้ จาก A ไป D มี 2 เส้นทาง คอื ABD และ ACD เส้นทางเช่อื มต่อ 2 เส้นจาก A ไป E มี 1 เส้นทาง คือ ABE เสน้ ทางเช่ือมต่อ 2 เสน้ จาก B ไป B มี 3 เส้นทาง คอื BAB , BDB และ BEB เส้นทางเชื่อมต่อ 2 เสน้ จาก B ไป C มี 2 เส้นทาง คือ BAC และ BDC เสน้ ทางเชอ่ื มต่อ 2 เสน้ จาก B ไป D มี 1 เสน้ ทาง คอื BED เส้นทางเชอ่ื มต่อ 2 เสน้ จาก B ไป E มี 1 เสน้ ทาง คือ BDE เสน้ ทางเชื่อมต่อ 2 เส้นจาก C ไป B มี 2 เสน้ ทาง คือ CAB และ CDB เส้นทางเชอ่ื มต่อ 2 เสน้ จาก C ไป C มี 2 เสน้ ทาง คือ CAC และ CDC เส้นทางเช่ือมต่อ 2 เส้นจาก C ไป E มี 1 เส้นทาง คือ CDE เสน้ ทางเชื่อมต่อ 2 เสน้ จาก D ไป A มี 2 เส้นทาง คอื DBA และ DCA เสน้ ทางเชอ่ื มต่อ 2 เสน้ จาก D ไป B มี 1 เสน้ ทาง คือ DEB เสน้ ทางเชื่อมต่อ 2 เส้นจาก D ไป D มี 3 เสน้ ทาง คือ DBD , DCD และ DED เส้นทางเชอ่ื มต่อ 2 เส้นจาก D ไป E มี 1 เส้นทาง คือ DBE เส้นทางเช่ือมต่อ 2 เสน้ จาก E ไป A มี 1 เส้นทาง คอื EBA เสน้ ทางเชอ่ื มต่อ 2 เสน้ จาก E ไป B มี 1 เส้นทาง คอื EDB เส้นทางเชอ่ื มต่อ 2 เส้นจาก E ไป C มี 1 เสน้ ทาง คือ EDC เอกสารประกอบการสอนรายวชิ าโครงสร้างขอ้ มลู และอลั กอรทิ ึม