โครงสร้างข้อมูลแบบต่าง ๆ

รูปภาพของ soraya-naka

โครงสร้างข้อมูลแบบต่างๆ


 


โครงสร้างข้อมูลแบบคิว (Queue) 


         คิวเป็นโครงสร้างข้อมูลแบบหนึ่งซึ่งมีลักษณะที่ว่า ข้อมูลที่นำเข้าไปเก็บก่อนจะถูกนำออกมาทำงานก่อน ส่วนข้อมูลที่เข้าไปเก็บทีหลังก็จะถูกนำออกมาใช้งานทีหลัง ขึ้นอยู่กับลำดับการเก็บข้อมูล จะเรียกลักษณะการทำงานแบบนี้ว่า เข้าก่อนออกก่อน หรือ First In First Out (FIFO)


                โครงสร้างข้อมูลแบบนี้เป็นโครงสร้างที่ปรากฏอยู่โดยทั่วๆ ไป โดยเฉพาะอย่างยิ่งในระบบปฏิบัติการคอมพิวเตอร์  ในระบบคมนาคม รวมทั้งในระบบการทดลองดาวเทียมด้วย


                ลักษณะของโครงสร้างแบบคิวจะเหมือนกับการเข้าแถวรอคอย ไม่ว่าจะเป็นการรอคอยอะไรก็ตาม หรือจะเรียกสั้นๆ ว่า เข้าคิวก็ได้ ด้วยคุณสมบัติที่เด่นชัดของการทำงานของโครงสร้างข้อมูลแบบคิวนี้ ว่าสิ่งใดที่เข้าก่อนย่อมต้องได้รับการทำงานก่อน เช่น การสั่งพิมพ์งานพร้อมกันหลายๆ คน โดยใช้เครื่องพิมพ์เครื่องเดียวกัน ทำให้ระบบจะต้องมีการจัดระบบให้มีการเข้าคิวรอคอยการทำงาน ถ้าใครสั่งพิมพ์ก่อนก็จะเข้าคิวไปรอการพิมพ์ในลำดับแรก ใครสั่งเป็นคนต่อไปก็จะต้องเข้าคิวรอจนกว่างานแรกจะทำการพิมพ์เสร็จ จึงจะมาทำงานกับคิวที่รออยู่ต่อไป


                  การสร้างคิว (Queue)


                คิวที่อยู่ในคอมพิวเตอร์สามารถจัดเก็บได้หลายลักษณะ แต่โดยทั่วไปแล้วจะใช้การจัดเก็บแบบลิงค์ลิสท์เดี่ยวหรือจัดเก็บโดยใช้อาร์เรย์


                ก่อนที่จะทำการสร้างคิวจะต้องทำความเข้าใจถึงโครงสร้างของคิว ซึ่งประกอบไปด้วย ตัวคิว ซึ่งในที่นี้ขอแทนด้วยอาร์เรย์  และจะต้องมีตัวชี้อีก 2 ตัว ได้แก่ ตัวชี้ F (Front Pointer) ชี้ไปที่สมาชิกตัวแรก และตัวชี้ R (Rear Pointer)  ชี้ไปที่สมาชิกตัวสุดท้ายของคิว โดยที่เวลาข้อมูลจะเข้าสู่คิวจะเข้าทาง R ส่วนเวลาที่ข้อมูลจะออกจากคิวจะออกทาง F


 


               


 


 


               เมื่อเริ่มต้นสร้างคิว คิวนั้นไม่มีค่าใดๆ ยังว่างเปล่า F และ R จะมีค่าเป็น 0 ทั้งคู่ คือไม่ได้ชี้ไปที่สมาชิกตัวใด การนำข้อมูลเข้าสู่คิวเรียกว่า การ Insertion ส่วนการนำข้อมูลออกจากคิวเรียกว่า การ Deletion


 


การ Insertion


                เป็นการนำข้อมูลเข้าสู่คิว โดยการที่จะนำข้อมูลเข้าสู่คิวนั้นจะแบ่งออกเป็น 2 กรณี คือ


                1. การนำข้อมูลเข้าไปในคิวว่าง โดยจะต้องดำเนินการให้พอยน์เตอร์ทั้ง 2 คือ F และ R ชี้ไปยังช่องแรกหรือตำแหน่งที่จะเก็บข้อมูลแรก


                2. การนำข้อมูลเข้าไปในคิวต่อจากข้อมูลเดิม จะต้องจัดการให้พอยน์เตอร์ R ชี้ไปยังช่องหรือตำแหน่งของข้อมูลที่นำเข้าไป ส่วนพอยน์เตอร์ F ยังคงชี้ไปยังช่องหรือตำแหน่งของข้อมูลที่นำเข้าไปเป็นข้อมูลแรก


               


การ Deletion


                เป็นการนำข้อมูลที่เก็บอยู่ในคิวออกจากคิว โดยการเมื่อทำการ Deletion ข้อมูลนั้นออกจากคิวแล้ว จะต้องมีการจัดการให้ตัวชี้คิว F ชี้ไปยังช่องหรือตำแหน่งต่อจากข้อมูลที่จะได้ทำการ Deletion ไปแล้ว ส่วนพอยน์เตอร์ R ชี้ไปยังช่องข้อมูลสุดท้ายเหมือนเดิม


 


               


 


โครงสร้างข้อมูลแบบสแตก (Stack)


 


                สแตกเป็นโครงสร้างข้อมูลที่ถูกกล่าวถึงมากโครงสร้างหนึ่ง ซึ่งมักจะใช้เป็นประโยชน์ในการอินเตอร์รัพต์  การกระโดดไปมาระหว่างโปรแกรมย่อย การเขียนโปรแกรมแบบเรียกใช้ตัวเอง (recursive) นอกจากนั้นแล้วโครงสร้างข้อมูลชนิดนี้มักจะใช้ช่วยในการเข้าไปในโครงสร้างแบบพิเศษ เช่น เครือข่าย หรือต้นไม้ โดยจะช่วยในการจำเส้นทาง และงานที่เรานำโครงสร้างแบบสแตกแล้วเราพบเห็นบ่อยๆ คือ การยกเลิกคำสั่ง (Undo) ในไมโครซอฟท์เวิร์ด


                สแตกเป็นโครงสร้างแบบเชิงเส้น ที่มีลักษณะที่ว่า การนำข้อมูลเข้าสู่สแตก (insertion) และการนำข้อมูลออกจากสแตก (deletion) สามารถจะทำได้ที่ปลายด้านหนึ่งของลิสท์ที่แทนสแตกเท่านั้น ดังนั้นอันดับของการนำสมาชิกเข้าและออกจากสแตกมีความสำคัญ คือ สมาชิกที่เข้าไปอยู่ในสแตกก่อนจะออกจากสแตกหลังสมาชิกที่เข้าไปใน สแตกทีหลัง นั่นคือ การเข้าทีหลังออกก่อน จึงเรียกลักษณะแบบนี้ว่า LIFO (Last  In  First  Out) 


                สแตกประกอบด้วยส่วนสำคัญ ๆ 2 ส่วน คือ


                1. ตัวชี้สแตก หรือ Stack Pointer   ซึ่งเป็นตัวควบคุมการนำสมาชิกเข้า  หรือออกจากสแตก  เป็นตัวใช้บอกว่าสแตกนั้นเต็มหรือยัง


                2. ส่วนสมาชิกของสแตก หรือจะเรียกอีกอย่างว่า Stack Element สมาชิกของสแตกนี้จะเป็นข้อมูลชนิดเดียวกันทั้งหมด


 


การสร้างสแตก


                ในการแทนโครงสร้างข้อมูลแบบสแตกจะใช้โครงสร้างข้อมูลแบบอาร์เรย์ หรือ ลิงค์ลิสท์ก็ได้ ทั้งนี้แล้วแต่ความเหมาะสมในการนำไปใช้ในการทำงาน ถ้าใช้การแทนที่ข้อมูลของสแตกด้วยอาร์เรย์ซึ่งเป็นการจัดสรรเนื้อที่หน่วยความจำแบบสแตติก ก็จะต้องมีการกำหนดขนาดของสแตกล่วงหน้าว่าจะมีขนาดเท่าใด แต่ถ้าเลือกการแทนที่ข้อมูลของสแตกด้วยลิงค์ลิสต์ซึ่งเป็นการจัดสรรเนื้อที่หน่วยความจำแบบไดนามิก สแตกจะไม่มีวันเต็มตราบใดที่ยังมีเนื้อที่ในหน่วยความจำ นั้นคือ หน่วยความจำจะถูกจัดสรรเมื่อมีการขอใช้จริงๆ ระหว่างการประมวลผลโปรแกรมผ่านตัวแปรชนิด pointer แต่ในที่นี้จะกำหนดให้ตัวสแตกเป็นแบบอาร์เรย์


                นอกจากตัวสแตกเองแล้ว ในการทำงานกับสแตกยังต้องกำหนดตัวแปรเพิ่มอีกหนึ่งตัวเพื่อเก็บตัวชี้สแตก (Stack Pointer) โดยเริ่มแรกในขณะที่สแตกยังไม่มีข้อมูล ตัวชี้สแตกก็จะชี้ที่ 0 (ยังไม่ได้ชี้ที่ช่องใดๆ ในสแตก)


                 การดำเนินงาน


                ทำงานกับโครงสร้างข้อมูลแบบสแตกได้แก่ การ PUSH และการ POP


                การ PUSH


                เป็นการกระทำหรือการทำงานของสแตกที่นำข้อมูลเข้าสู่สแตก โดยก่อนที่จะนำข้อมูลเข้านั้น จะต้องมีการจัดการให้ตัวชี้สแตกชี้ไปยังช่องหรือตำแหน่งต่อไปของส่วนของตัวสแตกก่อน ซึ่งเป็นช่องหรือตำแหน่งที่ว่างอยู่ไม่มีข้อมูล แล้วจึงค่อยทำการ PUSH ข้อมูลลงสู่สแตกในตำแหน่งที่ตัวชี้สแตกชี้อยู่


 



 


 


                 การ POP 


                เป็นการกระทำหรือการทำงานของสแตกที่นำข้อมูลที่เก็บอยู่ในสแตกออกจากสแตกมาใช้งาน โดยการ POP นี้ เมื่อทำการ POP ข้อมูลนั้นออกจากสแตกแล้ว จะต้องมีการจัดการให้ตัวชี้สแตกชี้ไปยังช่องหรือตำแหน่งก่อนหน้าข้อมูลที่ได้ทำการ POP ข้อมูลออกไป


 


 


ปรียบเทียบประสิทธิภาพของการสร้างสแตกด้วยอะเรย์และลิงค์ลิสต์


              การเลือกการแทนที่ข้อมูลสแตกด้วยอะเรย์ มีข้อจำกัดสำหรับขนาดของสแตกและจะต้องจองเนื้อที่เท่ากับขนาดที่ใหญ่ที่สุดของสแตกไว้เลย เพราะเป็นการจัดสรรเนื้อที่ในหน่วยความจำแบบสแตติก ส่วนการเลือกการแทนที่ข้อมูลสแตกด้วยลิงค์ลิสต์ ไม่มีข้อจำกัดของขนาดของสแตกและหน่วยความจำจะถูกใช้ก็ต่อเมื่อมีข้อมูลจริงๆ แล้วเท่านั้น เพราะเป็นการจัดสรรเนื้อที่หน่วยความจำแบบไดนามิก ซึ่งทำให้ประหยัดเนื้อที่ในหน่วยความจำมากกว่า แต่การเขียนโค้ดสำหรับการแทนที่ข้อมูลสแตกด้วยอะเรย์ง่ายกว่าการแทนที่ข้อมูลด้วยลิงค์ลิสต์


 


 


 


 


 


 


โครงสร้างข้อมูลลิ้งค์ลิสต์


                วิธีแก้ปัญหาในการย้ายข้อมูลที่พบในการจัดเก็บที่มีรูปแบบเรียงตามลำดับ(Sequential)เปลี่ยนมาใช้รูปแบบไม่เรียงตามลำดับ (Non-sequential)ซึ่งรูปแบบการเรียงตามลำดับจะมีสมาชิกเรียงต่อเนื่องติดกันในทางตรรกะ (Logical) และทางกายภาพ(Physical) เป็นแบบเดียวกัน แต่รูปแบบไม่เรียงตามลำดับสมาชิกต่อเนื่องติดกันในทางตรรกะ ส่วนทางกายภาพไม่จำเป็นต้องเหมือนกัน โดยในทางตรรกะจะแสดงด้วยแต่ละสมาชิกมีการชี้ (Point) ต้อไปยังสมาชิกตัวถัดไป สมาชิกทุกตัวในรายการจึงถูกเชื่อมต่อ (Link) เข้าด้วยกัน ดังรูปที่ 6.1 เป็นรายการเชื่อมต่อหรือเรียกว่าลิ้งค์ลิสต์ (Linked List) มีสมาชิก N ตัว แต่ละสมาชิกเรียกว่าโหนด (Node)


 


 


 


                จากรูปที่ 6.1 มีตัวแปรพอยน์เตอร์ First ชี้ไปยังโหนดแรกของรายการ แต่ละโหมดมีตัวเชื่อมเป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไปโดยโหนดสุดท้ายมีค่าเป็น NULL แสดงให้ทราบว่าไม่ได้ชี้ไปยังโหมดถัดไป แต่ละโหนดเป็นโครงสร้างข้อมูลเรคคอร์ด ประกอบด้วยสองส่วน คือ


               1.ส่วนเก็บข้อมูล (Info) ใช้เก็บข้อมูลข่าวสารที่มีโครงสร้างข้อมูลเบื้องต้นหรือเรียบง่าย


                2.ส่วนการเชื่อมต่อ (Next) เป็นตัวชี้หรือพอยน์เตอร์เก็บค่าแอดเดรสใช้อ้างไปยังโหนดถัดไปในหน่วยความจำ


                สำหรับในทางกายภาพของลิ้งค์ลิสต์ แต่ละดหนดไม่จำเป็นต้องอยู่ติดกัน อาจกระจัดกระจายไปยู่ส่วนไหนก็ได้ในหน่วยความจำโดยมีตัวเชื่อมชี้ไปยังตัวตำแหน่งของโหนดถัดไป


                ดังที่กล่าวในตอนต้นโครงสร้างสแตกและคิวมีการใช้อาร์เรย์ในการเก็บค่า สมาชิกทุกตัวจึงถูกจำกัดให้เป็นชนิดเดียวกัน(Homogenous) ซึ่งแก้ไขโดยเปลี่ยนมาใช้ลิ้งค์ลิสต์ที่มีโครงสร้างข้อมูลต่างกันได้ นอกจากนี้ยังมีผลดีในการปฏิบัติการแทรกข้อมูลหรือลบข้อมูล เพียงแต่ย้ายการชี้ของตัวแปรพอยน์เตอร์เท่านั้น ทำให้สมาชิกอื่นไม่มีผลกระทบ แต่ในกรณีค่าใช้จ่ายแล้วลิงค์ลิสต์จะสูงกว่าที่ต้องใช้พื้นที่เผิ่มมากขึ้นสำหรับส่วนการเชื่อมต่อเพื่อชี้ไปยังโหนดถัดไป และการค้นหาโหนดที่ต้องการใช้เวลามากเนื่องจากเป็นการค้นหาเรียงตามลำดับ (Sequential Search) ได้โหนดเดียวโดยเริ่มต้นที่โหนดแรกเสมอ


การปฏิบัติการพื้นฐานของลิงค์ลิสต์


                สิ่งสำคัญอย่างหนึ่งในการใช้โครงสร้างข้อมูลลิงค์ลิสต์ คือ ตัวแปรพอยน์เตอร์ (Pointer Variable) ซึ่งเก็บค่าเป็นตำแหน่งแอดเดรสในหน่วยความจำ (Memory Address) ในการปฏิบัติการกับลิ้งค์ลิสต์และให้มีความถูกต้องจะใช้ตัวแปรพอยน์เตอร์ในการจัดการเรื่องต่อไปนี้


1.ใช้ทดสอบกับค่า NULL


2.ใช้ทดสอบว่ามีค่าเท่ากับตัวแปรพอยน์เตอร์อื่น


3.กำหนดให้มีค่าเป็น NULL


4.กำหนดให้ชี้ไปยังโหนด


                ชุดปฏิบัติการของลิ้งค์ลิสต์ที่ทกวานร่วมกับตัวแปรพอยน์เตอร์ มีดังนี้


1.Node(P)  ส่งโหนดที่ถูกชี้ด้วยต้วแปรพอยน์เตอร์ P กลับมาให้


2.INFO(P) ส่งค่าในส่วนเก็บข้อมูลของโหนดที่ถูกชี้ด้วยตัวแปรพอยน์เตอร์ P กลับมาให้


3.Next(P)  ส่งพอยน์เตอร์ในส่วนการเชื่อมต่อขยองโหนดที่ถูกชี้ด้วยตัวแปรพอยน์เตอร์ P กลับมาให้


 


การแทรกโหนดไว้ในลิ้งค์ลิสต์


                อัลกอลิทึมในการแทรกโหนดใหม่เข้าไปไว้ในลิ้งค์ลิสต์ดังในตารางที่6.1


ตารางที่ 6.1 อัลกอริทึมการแทรกโหนดใหม่ลงในลิ้งค์ลิสสต์



 


               ตัวอย่างการแทรกโหนดใหม่ไว้ในลิ้งค์ลิสต์ โดยเริ่มต้นสร้างเป็นโหนด I ในหน่วยความจำกำหนดส่วนเก็บข้อมูลมีค่า L ส่วนการเชื่อมต่อมี่ค่าเป็น NULL ซึ่งมีตัวแปรพอยน์เตอร์ New ชี้อยู่ ดังในรูปที่ 6.2 และมีลิงค์ลิสต์ที่ต้องการแทรกโหนดใหม่เข้า าระหว่างโหนด 2 เป็นโหนดก่อนหน้า (Predecessor) และโหนด 3 เป็นโหนดถัดไป (Successor) ดังนั้นจึงกำหนดให้ตัวแปรพอยน์เตอร์ P ชี้ไปยังโหนด 2 และขั้นตอนในการแทรกประกอบด้วย



 


            1. Next(New) =Next (P) กำหนดให้ตัวชี้ของโหนด I เปลี่ยนไปชี้ยังโหนด 3 ซึ่งเป็นส่วนหลังของการแทรกโหนดใหม่ ในรูปที่ 6.3



 


            Next(P) =New กำหนดให้ตัวชี้ของโหนด 2 ที่มีตัวแปรพอยน์เตอร์ P ชี้อยู่เปลี่ยนไปชี้ยังโหนด I ที่มีตัวแปรพอยน์เตอร์ New ชี้อยู่ ในรูปที่ 6.4


 



 


             เมื่อการแทรกโหนดเสร็จสิ้น โหนด I จะมาต่อจากโหนดก่อนหน้าและแทนที่ลำดับของโหนดถัดไป การทำงานดังกล่าวจะมีเพียง 2 โหนดที่เดี่ยวขอ้งคือโหนดใหม่ I และโหนดที่ตัวแปรพอยน์เตอร์ P ชี้อยู่ ส่วนโหนดอื่นๆ ไม่ถูกเรียกใช้งานเรือเปลี่ยนแปลง



การลบโหนดออกจากลิ้งค์ลิสต์


            อัลกอริทึมในการลบโหนดออกจากลิ้งค์ลิสต์ดังในตารางที่ 6.2


ตารางที่ 6.2 อัลกอริทึมการลบโหนดออกจากลิ้งค์ลิสต์


 



 


 


 


 


 


 


 


 


โครงสร้างข้อมูลแบบต้นไม้ (Tree)  


โครงสร้างข้อมูลแบบต้นไม้ เป็นโครงสร้างชนิดไม่เชิงเส้นที่สำคัญที่สุดของโครงสร้างข้อมูล โครงสร้างต้นไม้มีความสัมพันธ์อย่างใกล้ชิดกับธรรมชาติของข่าวสารและวิธีการแปลงข่าวสารมาก โครงสร้างต้นไม้มีลักษณะที่สมชื่อของตนเอง เพราะมีลักษณะคล้ายกิ่งก้านของต้นไม้ ต้นไม้ตามธรรมชาติจะงอกจากล่างไปบน ส่วนโครงสร้างข้อมูลที่มีลักษณะต้นไม้นั้นเราจะวาดหรือให้เจริญจากบนลงมาล่างดังรูปจุดที่มีการแตกกิ่งก้านสาขาออกไปจะเรียกว่าโหนด (node) โดยข่าวสารจะเก็บอยู่ที่โหนด กิ่งที่ต่อระหว่างโหนดจะแสดงความสัมพันธ์ระหว่างโหนดเรียกว่าลิงค์ (link) อนึ่งตามรูป(ข) จุดปลายของกิ่งจะเรียกว่า โหนด ด้วย


 



 


(ก) ต้นไม้ปกติในธรรมชาติ (ข) ต้นไม้ในวิชาโครงสร้างข้อมูล


รูปลักษณะของโครงสร้างต้นไม้


 


1.นิยามของโครงสร้างต้นไม้
 เราสามารถนิยามโครงสร้างต้นไม้อย่างรีเคอร์ซีฟว่าเป็¹กลุ่มของโหนด T ดังนี้ ท มีโหนดพิเศษโหนดหนึ่งเรียกว่า รากหรือรูต (root node) , R ท โหนดอื่น ๆ ที่ไม่ใช่รูต สามารถถูกแบ่งย่อยออกเป็น n กลุ่ม โดยที่แต่ละกลุ่มไม่มีโหนดร่วมกันเลย สมมติให้ชื่อแต่ละกลุ่มเป็น T1,T2,…,Tn (n >= 0) ซึ่งแต่ละกลุ่มก็เป็นต้นไม้เหมือนกัน แต่จะเรียกว่าเป็น ต้นไม้ย่อย (subtree) ของโหนด R ดังรูปแสดงลักษณะของต้นไม้ตามนิยามแบบรีเคอร์ซีฟ



                            ซึ่งจะเห็นได้ว่า R เป็นรูตโหนดของต้นไม้ย่อย A,B,C,D
                             A เป็นรูตโหนดของต้นไม้ย่อย E,F,G
                             F เป็นรูตโหนดของต้นไม้ย่อย J
                            B เป็นรูตโหนดของต้นไม้ย่อย H , I เป็นต้น


1.1 การเรียกชื่อส่วนต่าง ๆ ของต้นไม้
                 ลักษณะของโครงสร้างต้นไม้มีลักษณะเหมือนการลำดับบรรพบุรุษ ดังนั้นชื่อที่ใช้จึงได้มาจากการลำดับบรรพบุรุษ เช่น FATHER , SON , GRANDSON ฯลฯ ที่ใช้บ่อยจะเป็นความสัมพันธ์ของพ่อ - ลูก (หรือ FATHER - SON )



 


1.2 ระดับของโหนด (Level)
      ระดับของโหนดหนึ่ง ๆ แสดงถึงหน่วยระยะทางตามแนวดิ่งของโหนดนั้นว่าอยู่ห่าง จากรูตโหนดเท่าไร ถ้ากำหนดว่ารูตโหนดของต้นไม้นั้นอยู่ที่ระดับ 1 และกิ่งทุกกิ่งมีความยาวเท่ากันหมดคือยาว 1 หน่วย เลขระดับของโหนดใด ๆ คือจำนวนกิ่งที่น้อยที่สุดจากรูตโหนดบวกหนึ่ง เช่น F มีเลขระดับเป็น 4 เป็นต้น


1.3 ดีกรีของโหนด (Level Degree)
      ดีกรีของโหนดคือจำนวนต้นไม้ย่อยของโหนดนั้น ตามรูปที่ 3 โหนด X มีดีกรี 1 โหนด A มีดีกรี 2 ส่วนโหนด H มีดีกรี 3 โหนด B มีดีกรี 1 และโหนด E มีดีกรี 0 เป็นต้น


1.4 โหนดที่เป็นใบ (Leaf Node หรือ Terminal Node)
     โหนดที่เป็นใบหมายถึงที่มีดีกรีเป็น 0 เช่นโหนด C,D,E,J,F,G ส่วนโหนดที่มีดีกรีไม่เท่ากับ 0 เรียกว่า โหนดภายใน หรือ interior node หรือ branch node


1.5 Predecessor และ Successor ( หรือ Ancester และ Descendant) predecessor
     หมายถึง ผู้มาก่อน successor หมายถึงผู้มาทีหลัง R,B,H จะเป็น predecessor ของโหนด E,I,F,J,E,F ไม่มี successor ส่วนโหนด J เป็น successor ของโหนด I และสรุปได้ว่าโหนด I จะเป็น predecessor ของโหนด J (หรือ J เป็น successor ของโหนด I ) ถ้าโหนด I และโหนด J มีกิ่ง (หนึ่งกิ่งหรือมากกว่า ) เชื่องถึงกัน
และโหนด I มีเลขหมายระดับน้อยกว่า โหนด J


1.6 Immediate Successor หรือ SON ของโหนด i immediate successor
      คือโหนดทั้งหลายของต้นไม้ย่อย i ที่มีค่าระดับต่ำกว่าโหนด i อยู่หนึ่ง เช่น SON ของโหนด H คือโหนด E,I,F


1.7 Immediate Predecessor หรือ FATHER ของโหนด I immediate predecessor
      คือโหนดที่มีค่าระดับสูงกว่าโหนด iอยู่หนึ่ง เช่น FATHER ของโหนด J คือ โหนด I , FATHER ของโหนด I คือโหนด H เป็นต้น


1.8 ป่า (Forest)
     ป่าหมายถึงกลุ่มของต้นไม้ที่เกิดจากการเอารูตโหนดของต้นไม้ต้นหนึ่งทิ้งไปตามรูปที่ 3 ถ้าลบรูตโหนด R ออกจะได้ต้นไม้ 3 ต้นประกอบขึ้นเป็น ป่าป่าที่ประกอบด้วยต้นไม้ A,B,X


2. ต้นไม้ที่มีแบบแผน (Ordered Tree)
       เราเรียกต้นไม้ A ว่าเป็นต้นไม้ที่มีแบบแผน ถ้าโหนดต่าง ๆ ของต้นไม้นั้นมีความสัมพันธ์ที่แน่นอนประการหนึ่ง เช่น ก่อน , ไปทางขวา , ไปทางซ้าย เป็นต้น ปกติต้นไม้จะถือว่าเป็นแบบที่ไม่มีแบบแผน นั่นคือไม่ได้กำหนดความสัมพันธ์ (เชิงตำแหน่ง) ระหว่างโหนด ฉะนั้นต้นไม้ตามรูป จึงถือว่าเหมือนกัน เพราะมีจำนวนโหนดและจำนวนต้นไม้ย่อยเท่ากัน นอกจากนี้เรายังสามารถ "หมุน" ต้นไม้ทั้งสองต้นนี้ให้อยู่ในแบบเดียวกันได้อีกด้วย แต่ถ้าเรากำหนดว่าต้นไม้ A และ B มีแบบแผน เราจะถือว่าต้นไม้ A และต้นไม้ B เป็นคนละต้นเพราะต้นไม้ A มีใบทางซ้าย 2 ใบ ส่วนต้นไม้ B มีใบทางขวา 2
ในหัวข้อที่ 4 เราจะศึกษาถึงต้นไม้ไบนารีซึ่งเป็นต้นไม้ชนิดมีแบบแผนที่มีความสำคัญต่อระบบคอมพิวเตอร์ ตลอดจนการเขียนโปรแกรมที่มีประสิทธิภาพ


3.การแทนโครงสร้างต้นไม้ในคอมพิวเตอร์
         ต้นไม้แบบที่กล่าวมาแล้วนี้สามารถเก็บในคอมพิวเตอร์ โดยอาศัยโครงสร้างของแต่ละโหนดดังรูปที่ 6 รูปที่ 6 โครงสร้างโหนดของต้นไม้ทั่วไป เนื่องจากแต่ละโหนดของต้นไม้จะมีกี่ SON ก็ได้ ดังนั้นจึงให้ส่วนลิงค์ของโหนดมี k ส่วน ถ้าโหนดหนึ่งในต้นไม้นั้นมี 3 SONs ก็จะได้ k = 3 ซึ่งแสดงว่าดครงสร้างของโหนดนั้นนอกจากจะมีส่วนข่าวสารแล้วยังจะมีส่วนลิงค์ 3 ส่วน คือ SON1 ,SON2, SON3 แต่ถ้าอีกโหนดหนึ่งในต้นไม้นั้นมี 5 SONs โครงสร้างของโหนดนั้นจะมีส่วนลิงค์ 5 ส่วนคือ SON1 ถึง SON5 จะเห็นได้ว่าการแทนโหนดลักษณะนี้ขนาดของพื้นที่ความจำที่ใช้สร้างแต่ละโหนดจะมีขนาดไม่คงที่ขึ้นอยู่กับจำนวน SON ของโหนดนั้น การจัดการกับโครงสร้างที่มีขนาดไม่เท่ากันตลอดนี้จะมีความยุ่งยากมากในแง่การจัดสรรและเลิกจัดสรรพื้นที่ความจำให้แก่โหนดวิธีหนึ่งที่จะผ่านข้อยุ่งยากนี้ไป
4.ต้นไม้แบบไบนารี (Binary Tree)
4.1 นิยาม ต้นไม้ไบนารี
      เป็น rooted binary tree ที่ว่างเปล่า หรือประกอบด้วยรูตโหนดและต้นไม้ไบนารี 2 กลุ่มที่ไม่มีโหนดร่วมกัน แต่ละกลุ่มจะมีชื่อเรียก (โดยตำแหน่งที่อยู่หรือที่เขียน) ว่าต้นไม้ย่อยทางซ้าย (left subtree) และต้นไม้ย่อยทางขวา (right subtree) ตามลำดับ คำว่า ว่างเปล่า ในนิยามหมายความว่า ต้นไม้ไบนารีต้นนั้นมีแต่รูตโหนดเพียงโหนดเดียวเท่านั้น โครงสร้างต้นไม้ที่ใช้ในการจัดการข่าวสารโดยคอมพิวเตอร์นั้น ส่วนใหญ่จะเป็นแบบโครงสร้างต้นไม้ไบนารี ลักษณะพิเศษจำเพาะของต้นไม้ไบนารีคือแต่ละโหนดมีดีกรีอย่างมากที่สุดเท่ากับ 2 นอกจากนี้ต้นไม้ไบนารียังเป็นต้นไม้ที่มีแบบแผนความสัมพันธ์เชิงตำแหน่งระหว่างโหนด นั่นคือที่โหนดใด ๆ ต้นไม้ย่อยของโหนดนั้นจะเรียกชื่อเฉพาะว่าเป็น ต้นไม้ย่อยทางขวา หรือ ต้นไม้ย่อยทางซ้าย ถ้าดูแค่โหนด จากโหนดหนึ่งจะเป็นความสัมพันธ์ FATHER และมีอีก 2 โหนด ต่อลงไปเป็น โหนดทางซ้าย หรือ left son หรือ LSON และโหนดทางขวา หรือ right son หรือ RSON ดังรูป



โครงสร้างต้นไม้ไบนารี LSON




                รูป ตัวอย่างของต้นไม้ไบนารีดูได้จากรูป(ก),(ข),(ค) ส่วนรูป (ง),(จ) และ (ฉ) นั้นไม่ใช่ต้นไม้ไบนารี เนื่องจากมีวงจรปิด


4.2 ต้นไม้ไบนารีแบบสมบูรณ์ (Complete Binary Tree)
      ต้นไม้ไบนารีแบบสมบูรณ์ หมายถึงต้นไม้ไบนารีที่แต่ละโหนดภายในมีโหนดย่อยซ้ายและขวา (นั่นคือแต่ละโหนดภายในมี left son และ right son ) และโหนดใบ (leaf nodes) ทั้งหลายอยู่ในระดับที่ n รูป (ก) เป็นต้นไม้ไบนารีแบบสมบูรณ์ที่มี 3 ระดับ ส่วนรูปที่ 11 เป็นต้นไม้ไบนารีแบบสมบูรณ์ที่มีโหนดใบอยู่ที่ระดับ 4 จะเห็นได้ว่าต้นไม้ไบนารีแบบสมบูรณ์ที่มีโหนดใบอยู่ที่ระดับ 3 จะมีโหนดทั้งหมดเท่ากับ 23 - 1 หรือ 7 และต้นไม้ไบนารีแบบสมบูรณ์ที่มีโหนดใบอยู่ที่ระดับ 4 จะมีโหนดเท่ากับ 24 - 1 หรือ 15 ซึ่งความสัมพันธ์ระหว่างระดับ (1) กับจำนวนโหนด (n) ในต้นไม้ไบนารีแบบสมบูรณ์ จะเขียนได้ดังนี้ n = 21 - 1



รูป ต้นไม้ไบนารีแบบสมบูรณ์ที่มีโหนดใบทั้งหมดอยู่ที่ระดับ 4


4.3 การแปลงต้นไม้ทั่วไปเป็นแบบไบนารี
     ในต้นไม้ทั่วไปโหนดแต่ละโหนดจะมีกี่ SON ก็ได้ ส่วนต้นไม้ไบนารีแต่ละโหนดจะมี SON ได้มากที่สุดเท่ากับ 2 SONs การแปลงต้นไม้ทั่วไปให้เป็นแบบไบนารีจะใช้หลักความจริงที่ว่า ในต้นไม้ทั่วไปแต่ละโหนดจะมี SON ที่อยู่ทางซ้ายสุด 1 SON และ SON โหนดนั้นจะมีพี่น้องถัดไป 1 โหนดเท่านั้น การแปลงนั้นแบ่งได้เป็น 2 ขั้นตอน คือ
ขั้นที่ 1 แปลงต้นไม้ทั่วไปโดยใช้หลักความสัมพันธ์ระหว่างโหนดเป็น leftmost son - next sibiling
ขั้นที่ 2 หมุนต้นไม้ที่แปลงแล้วไป 45 องศา จะได้ต้นไม้ไบนารีแบบปกติ การแปลงต้นไม้ทั่วไปเป็นแบบไบนารี


4.4 การแปลงป่าให้เป็นโครงสร้างแบบต้นไม้ไบนารี ในกรณีถ้ามีต้นไม้ทั่วไปหลาย ๆ ต้น เราสามารถแทนกลุ่มของต้นไม้นี้ โดยต้นไม้ไบนารี่ต้นเดียวได้ดังนี้


ขั้นที่ 1 ให้แปลงต้นไม้ทั่วไปแต่ละต้น ให้เป็นต้นไม้แบบไบนารี
ขั้นที่ 2 ให้เชื่อมรูตโหนดของต้นไม้ไบนารีแต่ละต้น โดยใช้ความสัมพันธ์ "พี่น้อง"
ขั้นที่ 3 หมุนต้นไม้ที่ได้ (ก)45 องศา ก็จะได้ต้นไม้ไบนารีที่แทนกลุ่มต้นไม้ทั่วไปที่กำหนดให้ การแปลงป่าให้เป็นต้นไม้ไบนารี


5.การแทนต้นไม้ไบนารีในหน่วยความจำ                                                                                                                                       ต้นไม้ไบนารีสามารถแทนได้ 2 แบบ คือ
1. การแทนโดยอาศัยพอยน์เตอร์
2. การแทนโดยอาศัยแอดเดรสของโหนด หรือการแทนแบบซีเควนเชียล (sequential)


5.1 การแทนโดยให้แต่ละโหนด
มีโครงสร้างโหนดสำหรับต้นไม้ไบนารี LLINK หรือ LSON เป็นพอยน์เตอร์ชี้ไปยังต้นไม้ย่อยทางซ้าย ส่วน RLINK หรือ RSON เป็นพอยน์เตอร์ชี้ไปยังต้นไม้ย่อยทางขวา ส่วนต้นไม้ไบนารีทั้งต้นจะแทนด้วย T โดยที่ T เป็นพอยน์เตอร์ชี้ไปยังรูตโหนด ถ้า T = L แสดงว่าต้นไม้ไบนารีนั้นว่างเปล่า T L แสดงว่าต้นไม้ไบนารีนั้นไม่ว่างเปล่า และ T จะเป็นแอดเดรสของรูตโหนด วิธีการแทนลักษณะนี้จะช่วยให้การทำ insertion และ deletion ของโหนดที่ส่วนกลางของต้นไม้ง่ายขึ้นมาก แต่เมื่อต้องการหา FATHER NODE ของ โหนด iอาจมีข้อยุ่งยากบ้างแต่ก็สามารถช่วยได้โดยอาศัยกลไกของสแตก


5.2 การแทนโดยอาศัยแอดเดรสของโหนด หรือการแทนแบบซีเควนเชียล วิธีนี้เป็นการแทนต้นไม้ไบนารีด้วยอาร์เรย์ 1 มิติอาร์เรย์เดียว การแทนแบบนี้เหมาะกับโครงสร้างต้นไม้ไบนารีแบบ full binary tree ที่สุด ซึ่งจะได้กล่าวต่อไป การแทนจะเริ่มต้นด้วยการให้หมายเลขแก่แต่ละโหนด ตั้งแต่ระดับ 1 ระดับ 2 …ไปเรื่อย ๆจนถึงระดับ k การให้ตัวเลขในแต่ละระดับให้จากซ้ายไปขวา โดยให้รูตโหนดมีหมายเลข 1 เสมอการให้ตัวเลขจะต้องถือว่าต้นไม้ไบนารีเป็นต้นไม้ไบนารีแบบสมบูรณ์ การให้แอดเดรสแก่ต้นไม้ไบนารีที่ถูกต่อเติมให้สมบูรณ์ เราจะต้องใช้อาร์เรย์ขนาด 15 ช่อง เพื่อเก็บต้นไม้ต้นนี้ ตำแหน่งของข่าวสารในต้นไม้จะตรงกับตำแหน่งในอาร์เรย์ การแทนต้นไม้ โดยใช้อาร์เรย์ โดยทั่วไปแล้วต้นไม้ไบนารีที่มีความสูง (ระบุโดยค่า level ที่มากที่สุด) h จะต้องใช้อาร์เรย์ที่มีขนาด 2h - 1 ช่อง เมื่อแทนโดยอาร์เรย์แล้ว เราจะต้องมีวิธีหาว่า "พ่อ" ของโหนด C คือใคร หรือว่า "ลูก" ของโหนด B คือใคร ดังนั้น FATHER , LSON ,RSON ของโหนด


 6.การเดินเข้าไปในโครงสร้างต้นไม้ (Tree Traversal)
     การนำต้นไม้ไบนารีมาใช้ประโยชน์นั้น หมายความว่าเราต้องมีวิธี เดิน หรือ traverse เข้าไปในต้นไม้อย่างมีแบบแผน เพื่อไป เยี่ยม โหนดต่าง ๆ โหนดละ 1 ครั้ง คำว่า เยี่ยมหมายถึงว่าเราจะไปยังโหนดเพื่อประมวลผลบางอย่างที่ต้องการกระทำกับโหนดนั้น เช่น หาข่าวสาร ดังนั้นผลลัพธ์จากการเดินเข้าไปในต้นไม้คือจะได้ข่าวสารที่เก็บ(หรือชี้) โดยโหนดเหล่านั้นออกมาในรูปเชิงเส้น ซึ่งนำไปใช้ประโยชน์ได้ ความคิดเริ่มต้นของการเดินก็คือ เราต้องเยี่ยมแต่ละโหนดพร้อมทั้งต้นไม้ย่อยทางซ้ายและทางขวาของโหนดนั้น ตามแนวความคิดนี้เราจะแยกต้นไม้ไบนารีออกเป็น 3 ส่วนคือ R,TL,TR โดยที่ R จะแทนรูตโหนด TL จะแทนต้นไม้ย่อยทางซ้ายและ TR จะแทนต้นไม้ย่อยทางขวา จะเห็นได้ว่าจะมีวิธีเดินอยู่ 6 ทางคือ R TL TR , TL RTR , TL TR R , TR RTL , R TR TL สัญลักษณ์ที่เขียนนี้เป็นลักษณะการนิยามแบบรีเคอร์ซีฟและลำดับจากซ้ายไปขวา ถึงแม้ว่าจะมีวิธีเดิน 6 วิธี แต่เราจะสนใจเพียง 3 วิธีแรกเท่านั้น ซึ่ง 3 วิธีแรกมีชื่อเรียกพิเศษและลักษณะรายละเอียดการเดินดังนี้


1) เดินแบบพรีออร์เดอร์ (pre - order traversal) - R TL TR ท เยี่ยม R ท เดินเข้าไปใน TL (ของ R) อย่างพรีออร์เดอร์ ท เดินเข้าไปใน TR (ของ R) อย่างพรีออร์เดอร์


2) เดินแบบอินออร์เดอร์ (in - order traversal) - TL RTR ท เดินเข้าไปใน TL (ของ R) อย่างอินออร์เดอร์ ท เยี่ยม R ท เดินเข้าไปใน TR (ของ R) อย่างอินออร์เดอร์


3) เดินแบบโพสออร์เดอร์ (post - order traversal) - TL TR R ท เดินเข้าไปใน TL (ของ R) อย่างโพสต์ออร์เดอร์ ท เดินเข้าไปใน TR (ของ R) อย่างโพสต์ออร์เดอร์ ท เยี่ยม R อีก 3 วิธี เกิดจากการสับเปลี่ยนตำแหน่ง TL และ TR ของ 3 วิธีที่กล่าวมาแล้ว ดังนั้น 3 วิธีหลังจะมีชื่อคล้าย ๆกับ 3 วิธีแรก เพียงแต่มีคำว่า reverse เพิ่มเข้าไปเท่านั้น ดังนั้น 3 วิธีหลังจะมีชื่อดังนี้


4) แบบ reverse pre - order traversal ( R TR TL )


5) แบบ reverse in - order traversal ( TR RTL )


6) แบบ reverse post - order traversal ( TR TL R)


6.1 การเดินเข้าแบบพรีออร์เดอร์ ( R TL TR ) สมมติมีต้นไม้ไบนารีตามรู» (ก) เราจะเดินเข้าไปในต้นไม้นี้อย่างพรีออร์เดอร์ได้ดังรูป (ข) (ก)จุดเริ่มต้นแสดงโดยพอยน์เตอร์ T (ข) ทิศทางการเยี่ยมโหนด



รูป ต้นไม้ไบนารี


 


6.2 การเดินเข้าแบบอินออร์เดอร์ (TL RTR ) การเดินแบบนี้มีลักษณะคล้ายกับการเดินแบบพรีออร์เดอร์ นั่นคือต้องท่องต้นไม้ย่อยทางซ้าย (TL )ให้ครบก่อน แล้วจึงค่อยท่องต้นไม้ทางขวาได้ การเดินแบบอินออร์เดอร์นี้เราจะเยี่ยมโหนดภายหลังจากที่ได้เดิน TL อย่างอินออร์เดอร์ครบหมดแล้วเท่านั้น เมื่อเดินอย่างอินออร์เดอร์แล้วจะได้ชุดลำดับของโหนดที่เยี่ยมดังนี้ DGBAECHFI


6.3 การเดินเข้าแบบโพสต์ออร์เดอร์ (TL TRR)เราเริ่มเดินเข้าไปใน TL จากโหนด A ถึงโหนด D จากนั้นก็เริ่มเดินเข้าไปใน TR ของโหนด D ซึ่งว่างเปล่า เป็นอันว่าเราได้เดิน TL, TR ของโหนด D ครบถ้วน ต่อไปก็ถึงคราว R ซึ่งก็ได้แก่การเยี่ยมโหนด D และได้โหนด D พิมพ์ออกมา เมื่อถึงตอนนี้ก็เท่ากับว่าเราได้เดิน TL ของโหนด B ครบถ้วน จึงเริ่มเดินเข้าไปใน TR ของโหนด B โดยเริ่มที่โหนด E ต่อไปก็เดินเข้าไปใน TL ของโหนด E อย่างโพสต์ออร์เดอร์อีก ได้โหนด G พิมพ์ออกมา (ตอนนี้ชุดของโหนดที่พิมพ์ออกมาแล้วคือ DG) จากนั้นก็เดินเข้าไปใน TR ของโหนด E อีก ได้โหนด H พิมพ์ออกมา ซึ่งเท่ากับเราได้เดิน TL , TR ของโหนด E ครบแล้ว จึงเยี่ยมโหนด E พิมพ์โหนด E ออกมา )ตอนนี้ชุดของโหนดที่พิมพ์ออกมาแล้วคือ DGHE) ณ จุดนี้เท่ากับว่าได้เดิน TL, TR ของโหนด B ครบถ้วนแล้ว จึงเยี่ยมโหนด B หลังจากนี้ เท่ากับเราได้เดิน TL ของโหนด A ครบถ้วน จึงหันไปเดิน TR ของโหนด A ซึ่งจะได้โหนด F และ C พิมพ์ออกมาตามลำดับ ขณะนี้เท่ากับว่าได้เดินเข้าไปใน TL และ TR ของโหนด A ครบถ้วนแล้ว จึงเยี่ยมโหนด A เป็นอันว่าสิ้นสุดการเดินอย่างโพสต์ออร์เดอร์เข้าไปในต้นไม้นี้ การเดินเข้าไปในโครงสร้างต้นไม้อย่างโพสต์ออร์เดอร์ ชุดของโหนดที่พิมพ์ออกมาคือ DGHEBFCA


 


 


 


 


โครงสร้างข้อมูลแบบกราฟ (GRAPH)


กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษแบบหนี่งของกราฟโดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูปและการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด


กราฟเป็นโครงสร้างข้อมูลประเภทหนึ่งที่แสดงความสัมพันธ์ระหว่าง vertex และ edge กราฟจะประกอบด้วยกลุ่มของ vertex ซึ่งแสดงในกราฟด้วยสัญลักษณ์รูปวงกลม และ กลุ่มของ edge (เส้นเชื่อมระหว่าง vertex) ใช้แสดงถึงความสัมพันธ์ระหว่าง vertex หากมี vertex ตั้งแต่ 2 vertex ขึ้นไปมีความสัมพันธ์กัน ใช้สัญลักษณ์เส้นตรงซึ่งอาจมีหัวลูกศร หรือไม่มีก็ได้


กราฟสามารถเขียนแทนด้วยสัญลักษณ์ ดังนี้


G = ( V , E )


G คือ กราฟ


V คือ กลุ่มของ vertex


E คือ กลุ่มของ edge


ศัพท์ที่เกี่ยวข้อง


1.เวอร์เทก (Vertex) หมายถึง โหนด


2.เอดจ (Edge) หมายถึง เส้นเชื่อมของโหนด


3.ดีกรี (Degree) หมายถึง จำนวนเส้นเข้าและออก ของโหนดแต่ละโหนด


4.แอดจาเซนท์โหนด (Adjacent Node) หมายถึง โหนดที่มีการเชื่อมโยงกัน


ตัวอย่างของกราฟในชีวิตประจำวัน เช่น กราฟของการเดินทางระหว่างเมือง ซึ่ง vertex คือ กลุ่มของเมืองต่างๆ และ edge คือ เส้นทางเดินระหว่างเมือง หรือ ในเครือข่ายคอมพิวเตอร์ (Computer Network) vertex ก็คือ กลุ่มของเครื่องคอมพิวเตอร์ หรือโหนดต่างๆ และ edge ก็คือ เส้นทางการติดต่อสื่อสารระหว่างโหนดต่างๆ เป็นต้น


ประเภทของกราฟ


แบ่งเป็น 3 ประเภทโดยแบ่งตามประเภทของ edge ได้ดังนี้


1. Direct Graph (กราฟแสดงทิศทาง) เป็นกราฟที่แสดงเส้นเชื่อมระหว่าง vertex โดแสดงทิศทางของการเชื่อมต่อด้วย


 


2. Undirected Graph กราฟที่แสดงเส้นเชื่อมต่อระหว่าง vertex แต่ไม่แสดงทิศทางของการเชื่อมต่อ



 



 


3. Cyclic Graph กราฟที่มีเส้นเชื่อมต่อระหว่าง vertex ที่ทำให้ vertex มีลักษณะเป็นวงจรปิด (Cycle) เส้นเชื่อมต่อระหว่าง vertex อาจจะแสดงทิศทางหรือไม่แสดงทิศทางการเชื่อมต่อก็ได้



 




 


เส้นทาง (Path)


           เส้นทางคือการเดินทางจาก vertex หนึ่งไปยังอีก vertex หนึ่งที่ต้องการ โดยผ่าน edge ที่เชื่อมระหว่าง vertex


         ความยาวของเส้นทาง (The length of path) คือ จำนวนของ edge ในเส้นทางเดินนั้น ว่ามีจำนวนเท่าไหร่ ในการเดินทางจาก vertex หนึ่ง ไปยังอีก vertex หนึ่ง ถ้าหากเส้นทางประกอบด้วย vertex จำนวน N ความยาวของเส้นทางจะเท่ากับ N-1 


 



 


ตัวอย่างเส้นทางการเดินทาง จาก vertex A ไป vertex D จะมีเส้นทางดังนี้


 



 


 


ตัวอย่างเส้นทางการเดินทาง จาก vertex A ไป vertex D จะมีเส้นทางดังนี้


 




 


การแทนที่กราฟด้วยเมตริกซ์


           โครงสร้างข้อมูลประเภทกราฟสามารถใช้เมตริกซ์มาแสดงแทนได้ โดยกราฟที่ประกอบด้วย vertex จำนวน N vertex สามารถแทนที่ด้วยเมตริกซ์ขนาด N x N โดยค่าในเมตริกซ์จะประกอบด้วย          ค่า 0 และ 1


 


         ค่า 0 จะใช้แทนไม่มี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง และ


 


         ค่า 1 จะใช้แทนมี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง


 


ตัวอย่างจากรูปกราฟแบบ Direct Graph


 



 


 


 


สามารถแทนที่กราฟด้วยเมตริกซ์ดังนี้



 



 


 


ตัวอย่าง หากเป็นกราฟแบบ Undirected Graph


 



 


 


 


 


การคำนวณเส้นทางระหว่าง vertex โดยใช้ Adjacency Matrix


 


           จากการแทนที่กราฟด้วยเมตริกซ์ เราสามารถนำเมตริกซ์ที่ได้มาคำนวณหาจำนวนเส้นทางระหว่าง vertex ต้นทางและปลายทางที่มีจำนวน edge ต่างๆ ได้


 



 


 


 


 


ตัวอย่างจากรูป สามารถคำนวณจำนวนเส้นทางระหว่าง vertex ที่มี edge จำนวน 3 เส้นได้ดังนี้


 


 



 


 


 


 


 


ตัวอย่างจากรูป สามารถคำนวณจำนวนเส้นทางระหว่าง vertex ที่มี edge จำนวน 4 เส้นได้ดังนี้


 


 


 



 

รูปภาพของ ssspoonsak

เนื่องจากมีข้อมูลบางส่วนหรือทั้งหมดได้ทำการคัดลอกมาแล้วไม่อ้างอิงแหล่งที่มาของข้อมูล

กรุณาอ้างอิงแหล่งที่มาของข้อมูลให้ชัดเจนด้วย ดูรูปแบบการทำเอกสารอ้างอิงได้ที่ http://www.thaigoodview.com/node/99177

มิฉะนั้นทางเว็บ thaigoodview.com จำเป็นต้องลบข้อมูลทั้งหมดออก

ขอขอบคุณ

ครูพูนศักดิ์ สักกทัตติยกุล

ผู้ดูแลเว็บไซต์ไทยกู๊ดวิว

 


ช่วยด้วยครับ
นักเรียนที่สร้างบล็อก กรุณาอย่าคัดลอกข้อมูลจากเว็บอื่นทั้งหมด
ควรนำมาจากหลายๆ เว็บ แล้ววิเคราะห์ สังเคราะห์ และเขียนขึ้นใหม่
หากคัดลอกทั้งหมด จะถูกดำเนินคดีตามกฎหมายจากเจ้าของลิขสิทธิ์
มีโทษทั้งจำคุกและปรับในอัตราสูง

ช่วยกันนะครับ 
ไทยกู๊ดวิวจะได้อยู่นานๆ ไม่ถูกปิดเสียก่อน
ขอขอบคุณในความร่วมมือครับ

มหาวิทยาลัยศรีปทุม ผู้ใหญ่ใจดี
 
 

 ช่วยด้วยครับ
นักเรียนที่สร้างบล็อก กรุณาอย่า
คัดลอกข้อมูลจากเว็บอื่นทั้งหมด
ควรนำมาจากหลายๆ เว็บ แล้ววิเคราะห์ สังเคราะห์ และเขียนขึ้นใหม่
หากคัดลอกทั้งหมด จะถูกดำเนินคดี
ตามกฎหมายจากเจ้าของลิขสิทธิ์
มีโทษทั้งจำคุกและปรับในอัตราสูง

ช่วยกันนะครับ 
ไทยกู๊ดวิวจะได้อยู่นานๆ 
ไม่ถูกปิดเสียก่อน

ขอขอบคุณในความร่วมมือครับ

อ่านรายละเอียด

ด่วน...... ขณะนี้
พระราชบัญญัติลิขสิทธิ์ (ฉบับที่ 2) พ.ศ. 2558 
มีผลบังคับใช้แล้ว 
ขอให้นักเรียนและคุณครูที่ใช้งาน
เว็บ thaigoodview ในการส่งการบ้าน
ระมัดระวังการละเมิดลิขสิทธิ์ด้วย
อ่านรายละเอียดที่นี่ครับ

 

สมาชิกที่ออนไลน์

ขณะนี้มี สมาชิก 0 คน และ ผู้เยี่ยมชม 248 คน กำลังออนไลน์