สรุปเนื้อหาบทเรียน "Data Structure"
เรื่อง Searching
การค้นหาข้อมูลแบ่งตามลักษณะการจัดเก็บได้ 2 อย่างคือ
1. การค้นหาข้อมูลภายใน (Internal Search)
2. การค้นหาข้อมูลภายนอก (External Search)
แบ่งตามลักษณะการค้นหาได้ 2 อย่างคือ
1. การค้นหาข้อมูลตามลำดับ (Linear Search)
ซึ่งการค้นหาแบบนี้มีเทคนิค 2 อย่างคือ
1.1 Unsorted Linear Search เป็นการค้นหาข้อมูลแบบเรียงลำดับทีละตัว เริ่มตั้งแต่ข้อมูลตัวแรก ไปเรื่อย ๆ จนกระทั่งพบข้อมูลที่ต้องการ หรือจนหมดทุกตัว
Algorithm
1. กำหนดให้ ตัวนับเริ่มต้นเป็นตัวแรกของข้อมูล
2. เปรียบเทียบข้อมูล ถ้า - พบข้อมูล ทำข้อ 5 - ไม่พบข้อมูล ทำข้อ 3
3. เพิ่มค่า ตัวนับ
4. ทำซ้ำข้อ 2
5. จบ
1.2 Sorted Linear Search เป็นการค้นหาข้อมูลแบบเรียงลำดับทีละตัว เริ่มตั้งแต่ข้อมูลตัวแรก ไปเรื่อย ๆ จนกระทั่งพบข้อมูลที่ต้องการ หรือจนค่าของข้อมูลตัวถัดไปมีค่ามากกว่า ซึ่งมีเงื่อนไขว่า ข้อมูลนั้นต้องมีการจัดเรียงแล้วเท่านั้น
Algorithm
1. กำหนดให้ ตัวนับเริ่มต้นเป็นตัวแรกของข้อมูล
2. เปรียบเทียบข้อมูล ถ้า -พบข้อมูล ทำข้อ 5 -ค่าของข้อมูลที่ต้องการค้นหา < ค่าของข้อมูลที่ตำแหน่ง ตัวนับ ทำข้อ 5
3. เพิ่มค่า ตัวนับ
4. ทำซ้ำข้อ 2
5. จบ
2. การค้นหาข้อมูลทวิภาค (Binary Search)
2.1 Binary Search in Array เป็นการค้นหาข้อมูลแบบทวิภาค โดยอาศัยการแบ่งข้อมูลที่มีอยู่ออกเป็นส่วน ๆ ซึ่งต้องหาค่ากลางของข้อมูลแล้วทำการเปรียบเทียบข้อมูลจากค่ากลางนั้น และข้อมูลต้องมีการจัดเรียงแล้วเท่านั้น
Algorithm
1. หาตำแหน่งกึ่งกลางโดย ได้จาก (Lo+Hi)/2
2. เปรียบเทียบ ถ้า
2.1 พบข้อมูล ทำข้อ 4
2.2 ข้อมูลมีค่าน้อยกว่าค่ากลางให้ ค่ากลางทางซ้าย
2.3 ข้อมูลมีค่ามากกว่าค่ากลางให้ ค่ากลางทางขวา
3. ทำซ้ำข้อ 2 จนกระทั่ง ตำแหน่ง Hi=Lo
4. จบ
2.2 Binary Search Tree เป็นการค้นหาข้อมูลแบบทวิภาค ซึ่งข้อมูลจัดอยู่ในรูปแบบของ Tree ที่เป็นลักษณะของ Binary Tree
Algorithm
1. สร้าง Binary Tree
2. เปรียบเทียบ กับ Node ที่อยู่ขณะนั้น ถ้า
2.1 ถ้าพบ ทำข้อ 4
2.2 ถ้า ค่าที่ต้องการค้นหา > Node ที่อยู่ขณะนั้น ให้หา Node ทางขวา
2.3 ถ้า ค่าที่ต้องการค้นหา < Node ที่อยู่ขณะนั้น ให้หา Node ทางซ้าย
3. ทำซ้ำข้อ 2 จน Node ไม่มี Child
4. จบ
วันเสาร์ที่ 19 กันยายน พ.ศ. 2552
DTS10-09/09/2552
สรุปเนื้อหาบทเรียน "Data Structure" เรื่อง Graph (ต่อ) และ Sorting
การท่องไปในกราฟ (graph traversal) คือ กระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับการท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียว แต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้นเพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำเครื่องหมายมาร์คบิตบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้วเพื่อไม่ให้เข้าไปเยือนอีก
สำหรับเทคนิคการท่องไปในกราฟมี 2 แบบดังนี้
การท่องแบบกว้าง (Breadth first traversal) วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับ จนกระทั่งเยือนหมดทุกโหนดในกราฟ
การท่องแบบลึก (Depth first traversal) การทำงานคล้ายกับการท่องทีละระดับของทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น ย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด Sorting
การเรียงลำดับข้อมูลเป็นเรื่องสำคัญมากเรื่องหนึ่งเนื่องจากทำให้ผู้ต้องการใช้ข้อมุลเช่น ผู้บริหาร,ผู้ปฏิบัติงาน (พนักงาน) สามารถทำความเข้าใจกับข้อมูลหรือทำการค้นหาข้อมูลได้ง่ายและเร็วยิ่งขึ้นตามที่ต้องการ
การเรียงข้อมูล สามารถแบ่งได้เป็น 2 ประเภทด้วยกันคือ
การเรียงข้อมูลแบบภายใน (Internal Sorting) คือ การเรียงลำดับข้อมูล โดยทั้งหมดต้องจัดเก็บอยู่ในหน่วยความจำหลัก (main memory) ที่มีการเข้าถึงข้อมูลได้เร็ว โดยไม่จำเป็นต้องใช้หน่วยความจำสำรอง เช่น ดิสค์ หรือเทปสำหรับการจัดเก็บชั่วคราว ใช้ในกรณีที่ข้อมูลไม่มากเกินกว่าพื้นที่ความจำที่กำหนดให้กับผู้ใช้แต่ละราย
การเรียงข้อมูลแบบภายนอก (External Sorting) คือ การ เรียงลำดับข้อมูลที่มีขนาดใหญ่เกินกว่าที่จะสามารถเก็บไว้ใน พื้นที่ความจำหลักที่กำหนดให้ได้ในคราวเดียว ดังนั้นข้อมูล ส่วนมากต้องเก็บไว้ในไฟล์ข้อมูลที่อยู่บนดิสค์ เทป เป็นต้น สำหรับการเรียงข้อมูลแบบภายนอกจะต้องคิดถึงเวลาที่ใช้ใน การถ่ายเทข้อมูลจากหน่วยความจำชั่วคราวกับหน่วยความจำหลัก ด้วยเช่นกัน
การเรียงลำดับแบบเลือก (Selection Sort) เป็นวิธีที่ง่ายที่สุดในการเรียงลำดับข้อมูล โดยเริ่มจาก - หาตำแหน่งของข้อมูลที่มีค่าน้อยที่สุดแล้วสลับค่าของตำแหน่งข้อมูลนั้นกับค่าข้อมูลในตำแหน่ง A(1) จะได้ A(1) มีค่าน้อยที่สุด - หาตำแหน่งของข้อมูลที่มีค่าน้อยที่สุดในกลุ่ม A(2), A(3),....,A(n) แล้วทำกับสลับค่าข้อมูลในตำแหน่ง A(2) อย่างนี้เรื่อยไปจน กระทั่งไม่เกิน N-1 รอบ ก็จะได้ข้อมูลที่เรียงลำดับจากน้อยไปมาก
การเรียงลำดับแบบแทรก (Insertion Sort) หลักการ คือ
1. อ่านข้อมุลที่ต้องการเรียงลำดับเข้ามาทีละตัวโดยเริ่มจากตัวแรกก่อน และหาตำแหน่งของข้อมูลที่ควรจะอยู่
2. หาที่ว่างสำหรับข้อ 1.
3. Insert หรือแทรกข้อมูล ณ ตำแหน่งในข้อ 2.
การเรียงลำดับแบบบับเบิล (Bubble Sort) วิธัการเรียงลำดับแบบบับเบิลจะทำการเปรียบเทียบข้อมูลที่อยู่ในตำแหน่งที่ติดกัน ถ้าข้อมูลไม่อยู่ใลำดับที่ถูกต้อง ก็จะทำการสลับตำแหน่งของข้อมูลที่เปรียบเทียบโดยที่การเปรียบเทียบจะเริ่มที่ตำแหน่งที่ 1 กับตำแหน่งที่ 2 ก่อน ต่อไปนี้เทียบกับ ตำแหน่งที่ 2 และตำแหน่งที่ 3 จนถึงตำแหน่งที่จัดเรียงแล้ว จากนั้นจะกลับไปเริ่มต้นการเปรียบเทียบอีกจนกระทั่งจัดเรียง เรียบร้อยหมดทุกตำแหน่ง ในวิธีแบบ Bubble Sort ค่าในการเปรียบเทียบที่น้อยที่สุดหรือมากที่สุด จะลอยขึ้นข้างบน เหมือนกับฟองอากาศ
การเรียงลำดับโดยการใช้ฐานเลข(radix sort) การเรียงลำดับแบบนี้การเรียงลำดับ จะอยู่บนพื้นฐานของการแทนตำแหน่งของตัวเลขที่ต้องการนำมาเรียงลำดับ จะเริ่มจากตัวที่มีเลขนัยสำคัญสูงที่สุด ดำเนินจนกระทั่งถึงตัวเลขที่มีเลขนัยสำคัญต่ำสุด การเรียงลำดับในวิธีนี้การเรียงลำดับ จะเรียงจากตัวเลขที่มีนัยสำคัญน้อยที่สุดก่อน เมื่อตัวเลขทั้งหมดถูกนำมาเรียงลำดับตามเลขนัยสำคัญที่สูงขึ้น ตัวเลขที่เหมือนกัน ในตำแหน่งน้น จะต่างกันในตำแหน่งของเลขนัยสำคัญที่น้อยกว่า การประมวลผลแบบนี้จะประมวลผลกับข้อมูลทั้งหมดได้ โดยที่ไม่ต้องมีการแบ่งข้อมูลแบบกลุ่มย่อย
การเรียงลำดับอย่างเร็ว(quick sort) จะแบ่งข้อมูลเป็นสองกลุ่ม โดยใน การจัดเรียงจะเลือกข้อมุลตัวใดตัวหนึ่งออกมา ซึ่งจะเป็นตัวที่แบ่งข้อมูลออกเป็นสองกลุ่ม โดยกลุ่มแรกจะต้องมีข้อมูลน้อยกว่า ตัวแบ่ง และกลุ่มที่มีข้อมูลน้อยกว่าตัวแบ่ง และอีกกลุ่มจะมีข้อมูลที่มากกว่าตัวแบ่ง ซึ่งเราเรียกตัวแบ่งว่า ตัวหลัก(pivot) ในการเลือกตัวหลักจะมีอิสระในการเลือกข้อมูลตัวใดก็ได้ที่เราต้องการ การเรียงลำดับแบบเร็วเหมาะกับข้อมูลที่มีการเรียกซ้ำ
การท่องไปในกราฟ (graph traversal) คือ กระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับการท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียว แต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้นเพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำเครื่องหมายมาร์คบิตบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้วเพื่อไม่ให้เข้าไปเยือนอีก
สำหรับเทคนิคการท่องไปในกราฟมี 2 แบบดังนี้
การท่องแบบกว้าง (Breadth first traversal) วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับ จนกระทั่งเยือนหมดทุกโหนดในกราฟ
การท่องแบบลึก (Depth first traversal) การทำงานคล้ายกับการท่องทีละระดับของทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น ย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด Sorting
การเรียงลำดับข้อมูลเป็นเรื่องสำคัญมากเรื่องหนึ่งเนื่องจากทำให้ผู้ต้องการใช้ข้อมุลเช่น ผู้บริหาร,ผู้ปฏิบัติงาน (พนักงาน) สามารถทำความเข้าใจกับข้อมูลหรือทำการค้นหาข้อมูลได้ง่ายและเร็วยิ่งขึ้นตามที่ต้องการ
การเรียงข้อมูล สามารถแบ่งได้เป็น 2 ประเภทด้วยกันคือ
การเรียงข้อมูลแบบภายใน (Internal Sorting) คือ การเรียงลำดับข้อมูล โดยทั้งหมดต้องจัดเก็บอยู่ในหน่วยความจำหลัก (main memory) ที่มีการเข้าถึงข้อมูลได้เร็ว โดยไม่จำเป็นต้องใช้หน่วยความจำสำรอง เช่น ดิสค์ หรือเทปสำหรับการจัดเก็บชั่วคราว ใช้ในกรณีที่ข้อมูลไม่มากเกินกว่าพื้นที่ความจำที่กำหนดให้กับผู้ใช้แต่ละราย
การเรียงข้อมูลแบบภายนอก (External Sorting) คือ การ เรียงลำดับข้อมูลที่มีขนาดใหญ่เกินกว่าที่จะสามารถเก็บไว้ใน พื้นที่ความจำหลักที่กำหนดให้ได้ในคราวเดียว ดังนั้นข้อมูล ส่วนมากต้องเก็บไว้ในไฟล์ข้อมูลที่อยู่บนดิสค์ เทป เป็นต้น สำหรับการเรียงข้อมูลแบบภายนอกจะต้องคิดถึงเวลาที่ใช้ใน การถ่ายเทข้อมูลจากหน่วยความจำชั่วคราวกับหน่วยความจำหลัก ด้วยเช่นกัน
การเรียงลำดับแบบเลือก (Selection Sort) เป็นวิธีที่ง่ายที่สุดในการเรียงลำดับข้อมูล โดยเริ่มจาก - หาตำแหน่งของข้อมูลที่มีค่าน้อยที่สุดแล้วสลับค่าของตำแหน่งข้อมูลนั้นกับค่าข้อมูลในตำแหน่ง A(1) จะได้ A(1) มีค่าน้อยที่สุด - หาตำแหน่งของข้อมูลที่มีค่าน้อยที่สุดในกลุ่ม A(2), A(3),....,A(n) แล้วทำกับสลับค่าข้อมูลในตำแหน่ง A(2) อย่างนี้เรื่อยไปจน กระทั่งไม่เกิน N-1 รอบ ก็จะได้ข้อมูลที่เรียงลำดับจากน้อยไปมาก
การเรียงลำดับแบบแทรก (Insertion Sort) หลักการ คือ
1. อ่านข้อมุลที่ต้องการเรียงลำดับเข้ามาทีละตัวโดยเริ่มจากตัวแรกก่อน และหาตำแหน่งของข้อมูลที่ควรจะอยู่
2. หาที่ว่างสำหรับข้อ 1.
3. Insert หรือแทรกข้อมูล ณ ตำแหน่งในข้อ 2.
การเรียงลำดับแบบบับเบิล (Bubble Sort) วิธัการเรียงลำดับแบบบับเบิลจะทำการเปรียบเทียบข้อมูลที่อยู่ในตำแหน่งที่ติดกัน ถ้าข้อมูลไม่อยู่ใลำดับที่ถูกต้อง ก็จะทำการสลับตำแหน่งของข้อมูลที่เปรียบเทียบโดยที่การเปรียบเทียบจะเริ่มที่ตำแหน่งที่ 1 กับตำแหน่งที่ 2 ก่อน ต่อไปนี้เทียบกับ ตำแหน่งที่ 2 และตำแหน่งที่ 3 จนถึงตำแหน่งที่จัดเรียงแล้ว จากนั้นจะกลับไปเริ่มต้นการเปรียบเทียบอีกจนกระทั่งจัดเรียง เรียบร้อยหมดทุกตำแหน่ง ในวิธีแบบ Bubble Sort ค่าในการเปรียบเทียบที่น้อยที่สุดหรือมากที่สุด จะลอยขึ้นข้างบน เหมือนกับฟองอากาศ
การเรียงลำดับโดยการใช้ฐานเลข(radix sort) การเรียงลำดับแบบนี้การเรียงลำดับ จะอยู่บนพื้นฐานของการแทนตำแหน่งของตัวเลขที่ต้องการนำมาเรียงลำดับ จะเริ่มจากตัวที่มีเลขนัยสำคัญสูงที่สุด ดำเนินจนกระทั่งถึงตัวเลขที่มีเลขนัยสำคัญต่ำสุด การเรียงลำดับในวิธีนี้การเรียงลำดับ จะเรียงจากตัวเลขที่มีนัยสำคัญน้อยที่สุดก่อน เมื่อตัวเลขทั้งหมดถูกนำมาเรียงลำดับตามเลขนัยสำคัญที่สูงขึ้น ตัวเลขที่เหมือนกัน ในตำแหน่งน้น จะต่างกันในตำแหน่งของเลขนัยสำคัญที่น้อยกว่า การประมวลผลแบบนี้จะประมวลผลกับข้อมูลทั้งหมดได้ โดยที่ไม่ต้องมีการแบ่งข้อมูลแบบกลุ่มย่อย
การเรียงลำดับอย่างเร็ว(quick sort) จะแบ่งข้อมูลเป็นสองกลุ่ม โดยใน การจัดเรียงจะเลือกข้อมุลตัวใดตัวหนึ่งออกมา ซึ่งจะเป็นตัวที่แบ่งข้อมูลออกเป็นสองกลุ่ม โดยกลุ่มแรกจะต้องมีข้อมูลน้อยกว่า ตัวแบ่ง และกลุ่มที่มีข้อมูลน้อยกว่าตัวแบ่ง และอีกกลุ่มจะมีข้อมูลที่มากกว่าตัวแบ่ง ซึ่งเราเรียกตัวแบ่งว่า ตัวหลัก(pivot) ในการเลือกตัวหลักจะมีอิสระในการเลือกข้อมูลตัวใดก็ได้ที่เราต้องการ การเรียงลำดับแบบเร็วเหมาะกับข้อมูลที่มีการเรียกซ้ำ
วันพุธที่ 2 กันยายน พ.ศ. 2552
DTS09-02/09/2552
สรุปเนื้อหาบทเรียน "Data Structure"
เรื่อง ทรี tree(ต่อ) และ เรื่องกราฟ Graph
ไบนารี่เสิร์ชทรี
เป็นไบนารี่ทรีที่รวบรวมค่าของ N เรคคอร์ดซึ่งเป็นคีย์ (Key) ตั้งแต่ K1 , K2 ,…….Kn โดยแต่ละโหนด Ri จะมี Ki เพียงคีย์เดียวสำหรับ i=1,2,….,N คีย์เป็นค่าสร้างความแตกต่าง (Identifier) ให้แต่ละโหนด ในการค้นหาโหนดที่ต้องการจะกระทำโดยค้นหาค่าของคีย์ และโหนด Ri ของไบนารี่เสิร์ชทรีจะถูกจัดการตามคุณสมบัติ ดังนี้
1. ทุก ๆ คีย์ของโหนดที่อยู่ในทรีย่อยด้านซ้ายของ Ri เป็นค่าที่มาก่อนหรือน้อยกว่าคีย์ของ Ri If Ri € Left (Ri) Then Kj <>
- ทุก ๆ คีย์ของโหนดที่อยู่ในทรีย่อยด้านขวาของ Ri เป็นค่าที่ตามหลังหรือมากกว่าคีย์ของ Ri
If Ri € Right (Ri) Then Kj > Ki จะได้ว่าคีย์ที่มาก่อนจะถูกพิจารณาตามลำดับเชิงเส้นและขึ้นกับลำดับการรวบรวม เมื่อพิจารณาตามคุณสมบัติที่ผ่านมาการค้นหาจะได้คีย์ A,B,C,D ตามลำดับและมีหลายวิธีที่จะจัดการกับไบนารี่เสิร์ชทรี จากรูปดังกล่าวจะมีไบนารี่เสิร์ชทรีหลายแบบแต่ลำดับของคีย์เหมือนกัน
วิธีการดึงโหนดออก แยกได้ 3 วิธี
1. กรณีโหนดที่จะดึงออกเป็นโหนดใบ สามารถดึงได้เลยเพราะไม่มีผลกระทบต่อโหนดอื่นๆ แล้วเป็นวิธีที่ง่ายที่สุด
2. กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยด้านซ้ายหรือทรีย่อยด้านขวาเพียงด้านใดด้านหนึ่ง สามารถทำได้เหมือนวิธีแรก เพียงให้โหนดแม่ของโหนดที่ต้องการดึงออกชี้ไปยังโหนดลูกของโหนดนั้นแทน
3. กรณีโหนดที่ต้องการดึงออกมีทั้งทรีย่อยด้านซ้ายและทรีย่อยด้านขวา ต้องทำการเลือกว่าจะนำทรีย่อยด้านใดมาแทนโหนดที่ถูกดึงออก
กราฟ (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) หมายถึง โหนดที่มีการเชื่อมโยงกัน
Graph แบ่งเป็น
1. Directed Graph (Digraph) (Arc) แบบระบุทิศทาง
2. Undirected Graph แบบไม่ระบุทิศทาง
การเก็บข้อมูลในหน่วยความจำสามารถทำได้ 2 แบบ ดังนี้
1. Adjacency Matrix (แอดจาเซนซี เมตริก) : ใช้อาร์เรย์เก็บข้อมูล
2. Adjacency List (แอดจาเซนซี ลิส) : ใช้ลิงค์ลิสต์เก็บข้อมูล
Adjacency Matrix
เป็นโครงสร้างที่ประกอบไปด้วยโหนดและเส้นเชื่อมต่อที่บอกถึงเส้นทางของการเดินทาง หรือความสัมพันธ์ในทิศทางซึ่งสามารถนำมาแทนความสัมพันธ์นั้นด้วยการกำหนดเมตริกซ์ n x n
Mk เป็นเมทริกซ์ของกราฟใด ๆ k คือทางเดินที่มีความยาว k จากโหนดหนึ่งไปอีกโหนดหนึ่ง
Adjacency Matrix
0 : ไม่เป็นแอดจาเซนซีกัน
1 : เป็นแอดจาเซนซีกัน
การท่องไปในกราฟ
เป็นการไปเยือนโหนดในกราฟ ซึ่งแต่ละโหนดจะถูกเยือนเพียงครั้งเดียว แต่กราฟนั้นมาหลายเส้นทางเมื่อเยือนแล้วต้องทำเครื่องหมายว่าได้เยือนเรียบร้อย การท่องไปในกราฟมี 2 แบบ คือ
1.การท่องแบบกว้าง เป็นการกำหนดโหนดที่จะเยือนหรือโหนดเริ่มต้นแล้วทำการเยือนไปยังโหนดที่ใกล้เคียงจนกระทั่งครบทุกโหนด
2.การท่องแบบลึก โดยกำหนดเริ่มต้นที่โหนดแรกแล้วเยือนโหนดถัดไปตามแนววิถีจนถึงปลายวิถี แล้วย้อนกลับมาเพื่อเยือนโหนดอื่นๆ
เรื่อง ทรี tree(ต่อ) และ เรื่องกราฟ Graph
ไบนารี่เสิร์ชทรี
เป็นไบนารี่ทรีที่รวบรวมค่าของ N เรคคอร์ดซึ่งเป็นคีย์ (Key) ตั้งแต่ K1 , K2 ,…….Kn โดยแต่ละโหนด Ri จะมี Ki เพียงคีย์เดียวสำหรับ i=1,2,….,N คีย์เป็นค่าสร้างความแตกต่าง (Identifier) ให้แต่ละโหนด ในการค้นหาโหนดที่ต้องการจะกระทำโดยค้นหาค่าของคีย์ และโหนด Ri ของไบนารี่เสิร์ชทรีจะถูกจัดการตามคุณสมบัติ ดังนี้
1. ทุก ๆ คีย์ของโหนดที่อยู่ในทรีย่อยด้านซ้ายของ Ri เป็นค่าที่มาก่อนหรือน้อยกว่าคีย์ของ Ri If Ri € Left (Ri) Then Kj <>
- ทุก ๆ คีย์ของโหนดที่อยู่ในทรีย่อยด้านขวาของ Ri เป็นค่าที่ตามหลังหรือมากกว่าคีย์ของ Ri
If Ri € Right (Ri) Then Kj > Ki จะได้ว่าคีย์ที่มาก่อนจะถูกพิจารณาตามลำดับเชิงเส้นและขึ้นกับลำดับการรวบรวม เมื่อพิจารณาตามคุณสมบัติที่ผ่านมาการค้นหาจะได้คีย์ A,B,C,D ตามลำดับและมีหลายวิธีที่จะจัดการกับไบนารี่เสิร์ชทรี จากรูปดังกล่าวจะมีไบนารี่เสิร์ชทรีหลายแบบแต่ลำดับของคีย์เหมือนกัน
วิธีการดึงโหนดออก แยกได้ 3 วิธี
1. กรณีโหนดที่จะดึงออกเป็นโหนดใบ สามารถดึงได้เลยเพราะไม่มีผลกระทบต่อโหนดอื่นๆ แล้วเป็นวิธีที่ง่ายที่สุด
2. กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยด้านซ้ายหรือทรีย่อยด้านขวาเพียงด้านใดด้านหนึ่ง สามารถทำได้เหมือนวิธีแรก เพียงให้โหนดแม่ของโหนดที่ต้องการดึงออกชี้ไปยังโหนดลูกของโหนดนั้นแทน
3. กรณีโหนดที่ต้องการดึงออกมีทั้งทรีย่อยด้านซ้ายและทรีย่อยด้านขวา ต้องทำการเลือกว่าจะนำทรีย่อยด้านใดมาแทนโหนดที่ถูกดึงออก
กราฟ (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) หมายถึง โหนดที่มีการเชื่อมโยงกัน
Graph แบ่งเป็น
1. Directed Graph (Digraph) (Arc) แบบระบุทิศทาง
2. Undirected Graph แบบไม่ระบุทิศทาง
การเก็บข้อมูลในหน่วยความจำสามารถทำได้ 2 แบบ ดังนี้
1. Adjacency Matrix (แอดจาเซนซี เมตริก) : ใช้อาร์เรย์เก็บข้อมูล
2. Adjacency List (แอดจาเซนซี ลิส) : ใช้ลิงค์ลิสต์เก็บข้อมูล
Adjacency Matrix
เป็นโครงสร้างที่ประกอบไปด้วยโหนดและเส้นเชื่อมต่อที่บอกถึงเส้นทางของการเดินทาง หรือความสัมพันธ์ในทิศทางซึ่งสามารถนำมาแทนความสัมพันธ์นั้นด้วยการกำหนดเมตริกซ์ n x n
Mk เป็นเมทริกซ์ของกราฟใด ๆ k คือทางเดินที่มีความยาว k จากโหนดหนึ่งไปอีกโหนดหนึ่ง
Adjacency Matrix
0 : ไม่เป็นแอดจาเซนซีกัน
1 : เป็นแอดจาเซนซีกัน
การท่องไปในกราฟ
เป็นการไปเยือนโหนดในกราฟ ซึ่งแต่ละโหนดจะถูกเยือนเพียงครั้งเดียว แต่กราฟนั้นมาหลายเส้นทางเมื่อเยือนแล้วต้องทำเครื่องหมายว่าได้เยือนเรียบร้อย การท่องไปในกราฟมี 2 แบบ คือ
1.การท่องแบบกว้าง เป็นการกำหนดโหนดที่จะเยือนหรือโหนดเริ่มต้นแล้วทำการเยือนไปยังโหนดที่ใกล้เคียงจนกระทั่งครบทุกโหนด
2.การท่องแบบลึก โดยกำหนดเริ่มต้นที่โหนดแรกแล้วเยือนโหนดถัดไปตามแนววิถีจนถึงปลายวิถี แล้วย้อนกลับมาเพื่อเยือนโหนดอื่นๆ
สมัครสมาชิก:
บทความ (Atom)