DTS 11-16/09/52

Summary B4 Final


ทรี (Tree)
เป็นโครงสร้างข้อมูลที่ความสัมพันธ์
ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับ
ชั้น (Hierarchical Relationship)เช่น แผนผังองค์ประกอบของหน่วยงานต่าง ๆ
โครงสร้างสารบัญหนังสือ เป็นต้น

การท่องไปในไบนารีทรี
วิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบ
แผน สามารถเยือนโหนดทุก ๆ โหนด ๆ ละหนึ่งครั้ง
วิธีการท่องไปในทรีรี 6 วิธี คือ NLR LNR LRN NRL RNL และ RLN
แต่วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรก
เท่านั้นคือ NLR LNR และ LRN ซึ่งลักษณะการนิยามเป็นนิยามแบบ รีเคอร์ซีฟ(Recursive) ซึ่งขั้นตอนการท่องไปในแต่ละแบบมีดังนี้


1. การท่องไปแบบพรีออร์เดอร์
(Preorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี
NLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์

2.การท่องไปแบบอินออร์เดอร์
(Inorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธี LNR
มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์

3. การท่องไปแบบโพสออร์เดอร์
(Postorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
(3) เยือนโหนดราก

ไบนารีเซิร์ชทรี
ไบนารีเซิร์ชทรี (Binary Search Tree)
เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนด
ในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุก
โหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่า
หรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวา
และในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกัน

กราฟที่มีการเปลี่ยนแปลงตลอดเวลา
อาจจะใช้วิธีแอดจาเซนซีลิสต์
(Adjacency List) ซึ่งเป็นวิธีที่คล้ายวิธี
จัดเก็บกราฟด้วยการเก็บโหนดและพอยน์
เตอร์ แต่ต่างกันตรงที่ จะใช้ ลิงค์ลิสต์แทน
เพื่อความสะดวกในการเปลี่ยนแปลงแก้ไข
การท่องไปในกราฟ
1. การค้นหาแบบกว้าง (Breadth-first Search)
2. การค้นหาแบบลึก (Depth-first Search)

กราฟ มีน้ำหนัก หมายถึง กราฟที่ทุก
เอดจ์ มีค่าน้ำหนักกำกับ ซึ่งค่าน้ำหนักอาจสื่อถึง
ระยะทาง เวลา ค่าใช้จ่าย เป็นต้น นิยมนำไปใช้
แก้ปัญหาหลัก ๆ 2 ปัญหา คือ
1. การสร้างต้นไม้ทอดข้ามน้อยที่สุด
(Minimum Spanning Trees :MST)
2. การหาเส้นทางที่สั้นที่สุด(Shortest path)

Sorting
การเรียงลำดับแบบเร็ว (quick sort)
เป็นวิธีการเรียงลำดับที่ใช้เวลาน้อยเหมาะสำหรับข้อมูลที่มีจำนวนมากที่ต้องการความรวดเร็ว
ในการทำงาน วิธีนี้จะเลือกข้อมูลจากกลุ่มข้อมูลขึ้นมาหนึ่งค่าเป็นค่าหลัก แล้วหาตำแหน่งที่ถูกต้อง
ให้กับค่าหลักนี้ เมื่อได้ตำแหน่งที่ถูกต้องแล้ว ใช้ค่าหลักนี้เป็นหลักในการแบ่งข้อมูลออกเป็นสองส่วน
ถ้าเป็นการเรียงลำดับจากน้อยไปมาก ส่วนแรกอยู่ในตอนหน้าข้อมูล ทั้งหมดจะมีค่าน้อยกว่าค่าหลักที่เป็นตัวแบ่งส่วน
อีกส่วนหนึ่งจะอยู่ในตำแหน่งตอนหลังข้อมูลทั้งหมด จะมีค่ามากกว่าค่าหลัก แล้วนำแต่ละ
ส่วนย่อยไปแบ่งย่อยในลักษณะเดียวกันต่อไปจนกระทั่งแต่ละส่วนไม่สามารถแบ่งย่อยได้อีก
ต่อไปจะได้ข้อมูลที่มีการเรียงลำดับตามที่ต้องการถ้าเป็นการเรียงลำดับจากน้อยไปมากการเปรียบเทียบเพื่อหาตำแหน่งให้กับค่าหลัก
ตัวแรกเริ่มจากข้อมูลในตำแหน่งแรกหรือสุดท้ายก็ได้ถ้าเริ่มจากข้อมูลที่ตำแหน่งที่ 1 เป็นค่าหลัก พิจารณา
เปรียบเทียบค่าหลักกับข้อมูลในตำแหน่งสุดท้ายถ้าค่าหลักมีค่าน้อยกว่าให้เปรียบเทียบกับข้อมูลในตำแหน่งรอง
สุดท้ายไปเรื่อย ๆ จนกว่าจะพบค่าที่น้อยกว่าค่าหลัก แล้วให้สลับตำแหน่งกัน
หลังจากสลับตำแหน่งแล้วนำค่าหลักมาเปรียบเทียบกับข้อมูล ในตำแหน่งที่ 2, 3,
ไปเรื่อย ๆ จนกว่าจะพบค่าที่มากกว่าค่าหลักสลับตำแหน่งเมื่อเจอข้อมูลที่มากกว่าค่าหลัก ทำ
เช่นนี้ไปเรื่อย ๆ จนกระทั่งได้ตำแหน่งที่ถูกต้องของค่าหลักนั้น ก็จะแบ่งกลุ่มข้อมูลออกเป็นสอง
ส่วน ส่วนแรกข้อมูลทั้งหมดมีค่าน้อยกว่าค่าหลักและส่วนที่สองข้อมูลทั้งหมดมีค่ามากกว่าค่าหลัก

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


วิธีการค้นหาข้อมูล
1. การค้นหาแบบเชิงเส้นหรือการค้นหาตามลำดับ(Linear)เป็นวิธีที่ใช้กับข้อมูลที่ยังไม่ได้เรียงลำดับ
หลักการ คือ ให้นำข้อมูลที่จะหามาเปรียบเทียบกับข้อมูลตัว
แรกในแถวลำดับ
ถ้าไม่เท่ากันให้เปรียบเทียบกับข้อมูลตัวถัดไป
ถ้าเท่ากันให้หยุดการค้นหา หรือการค้นหาจะหยุดเมื่อพบ
ข้อมูลที่ต้องการหรือหาข้อมูลทุกจำนวนในแถวลำดับแล้วไม่พบ
2. การค้นหาแบบเซนทินัล (Sentinel)เป็นวิธีที่การค้นหาแบบเดียวกับวิธีการค้นหาแบบเชิงเส้น
แต่ประสิทธิภาพดีกว่าตรงที่เปรียบเทียบน้อยครั้งกว่า พัฒนามาจากอัลกอริทึมแบบเชิงเส้น
หลักการ1) เพิ่มขนาดของแถวลำดับ ที่ใช้เก็บข้อมูลอีก 1 ที่
2) นำข้อมูลที่จะใช้ค้นหาข้อมูลใน Array ไปฝากที่ต้นหรือ ท้าย
Array
3) ตรวจสอบผลลัพธ์จากการหา
โดยตรวจสอบจากตำแหน่งที่พบ ถ้าตำแหน่งที่พบมีค่าเท่ากับ n-1
แสดงว่าหาไม่พบ นอกนั้นถือว่าพบข้อมูลที่ค้าหา

3. การค้นหาแบบไบนารี (Binary Search)
การค้นหาแบบไบนารีใช้กับข้อมูลที่ ถูกจัดเรียงแล้วเท่านั้น
หลักการของการค้นหาคือ ข้อมูลถูกแบ่งออกเป็นสองส่วน
แล้วนำค่ากลางข้อมูลมาเปรียบเทียบกับคีย์ที่ต้องการหา
1.หาตัวแทนข้อมูลเพื่อนำมาเปรียบเทียบกับค่าที่ต้องการค้น
ตำแหน่งตัวแทนข้อมูลหาได้จากสูตร
mid = (low+high)/2
mid คือ ตำแหน่งกลาง ,low คือ ตำแหน่งต้นแถวลำดับ
high คือ ตำแหน่งท้ายของแถวลำดับ
2.นำผลการเปรียบเทียบกรณีที่หาไม่พบมาใช้ในการค้นหารอบต่อไป

DTS 10-09/09/52

สรุปบทเรียน การเรียงลำดับ

การเรียงลำดับข้อมูลเป็นเรื่องสำคัญมากเรื่องหนึ่งเนื่องจากทำให้ผู้ต้องการใช้ข้อมุลเช่น ผู้บริหาร,ผู้ปฏิบัติงาน (พนักงาน) สามารถทำความเข้าใจกับข้อมูลหรือทำการค้นหาข้อมูลได้ง่ายและเร็วยิ่งขึ้นตามที่ต้องการ
การเรียงลำดับที่ดี และเหมาะสมกับระบบงาน เพื่อให้ประสิทธิภาพในการ
ทำงานสูงสุด ควรจะต้องคำนึงถึงสิ่งต่าง ๆ ดังต่อไปนี้
(1) เวลาและแรงงานที่ต้องใช้ในการเขียนโปรแกรม
(2) เวลาที่เครื่องคอมพิวเตอร์ต้องใช้ในการทำงานตามโปรแกรมที่เขียน
(3) จำนวนเนื้อที่ในหน่วยความจำหลักมีเพียงพอหรือไม่

วิธีการเรียงลำดับ

วิธีการเรียงลำดับสามารถแบ่งออกเป็น2 ประเภท คือ
(1)การเรียงลำดับแบบภายใน (internal sorting)เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ใน
หน่วยความจำหลัก เวลาที่ใช้ในการเรียงลำดับจะคำนึงถึงเวลาที่ใช้ในการเปรียบเทียบและเลื่อนข้อมูลภายในความจำหลัก
(2) การเรียงลำดับแบบภายนอก
(external sorting) เป็นการเรียงลำดับข้อมูลที่
เก็บอยู่ในหน่วยความจำสำรอง ซึ่งเป็นการ
เรียงลำดับข้อมูลในแฟ้มข้อมูล (file) เวลาที่ใช้ใน
การเรียงลำดับต้องคำนึงถึงเวลาที่เสียไประหว่าง
การถ่ายเทข้อมูลจากหน่วยความจำหลักและ
หน่วยความจำสำรองนอกเหนือจากเวลาที่ใช้
ในการเรียงลำดับข้อมูลแบบภายใน

การเรียงลำดับแบบเลือก (selection sort)ทำการเลือกข้อมูลมาเก็บในตำแหน่งที่ ข้อมูลนั้นควรจะอยู่ทีละ
ตัว โดยทำการค้นหาข้อมูลนั้นในแต่ละรอบแบบเรียงลำดับ
ถ้าเป็นการเรียงลำดับจากน้อยไปมาก
1. ในรอบแรกจะทำการค้นหาข้อมูลตัวที่มีค่าน้อยที่สุดมาเก็บ
ไว้ที่ตำแหน่งที่ 1
2. ในรอบที่สองนำข้อมูลตัวที่มีค่าน้อยรองลงมาไปเก็บไว้ที่
ตำแหน่งที่สอง
3. ทำเช่นนี้ไปเรื่อย ๆ จนกระทั่งครบทุกค่า
ในที่สุดจะได้ข้อมูลเรียงลำดับจากน้อยไปมากตามที่ต้องการ
การจัดเรียงลำดับแบบเลือกเป็นวิธีที่ง่ายและ
ตรงไปตรงมา แต่มีข้อเสียตรงที่ใช้เวลาในการจัดเรียงนาน
เพราะแต่ละรอบต้องเปรียบเทียบกับข้อมูลทุกตัว ถ้ามี
จำนวนข้อมูลทั้งหมด n ตัว ต้องทำการเปรียบเทียบทั้งหมด
n – 1 รอบ และจำนวนครั้งของการเปรียบเทียบในแต่ละ
รอบเป็นดังนี้
รอบที่ 1 เปรียบเทียบเท่ากับ n −1 ครั้ง
รอบที่ 2 เปรียบเทียบเท่ากับ n – 2 ครั้ง
...
รอบที่ n – 1 เปรียบเทียบเท่ากับ 1 ครั้ง

การเรียงลำดับแบบฟอง (Bubble Sort)
เป็นวิธีการเรียงลำดับที่มีการเปรียบเทียบข้อมูลใน
ตำแหน่งที่อยู่ติดกัน
1. ถ้าข้อมูลทั้งสองไม่อยู่ในลำดับที่ถูกต้องให้สลับตำแหน่ง
ที่อยู่กัน
2. ถ้าเป็นการเรียงลำดับจากน้อยไปมากให้นำข้อมูลตัวที่มี
ค่าน้อยกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มีค่ามาก ถ้า
เป็นการเรียงลำดับจากมากไปน้อยให้นำข้อมูล ตัวที่มี
ค่ามากกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มีค่าน้อย
ในวิธีแบบ Bubble Sort ค่าในการเปรียบเทียบที่น้อยที่สุดหรือมากที่สุด จะลอยขึ้นข้างบน เหมือนกับฟองอากาศ

การเรียงลำดับอย่างเร็ว (quick sort)จะแบ่งข้อมูลเป็นสองกลุ่ม โดยใน การจัดเรียงจะเลือกข้อมุลตัวใดตัวหนึ่งออกมา ซึ่งจะเป็นตัวที่แบ่งข้อมูลออกเป็นสองกลุ่ม โดยกลุ่มแรกจะต้องมีข้อมูลน้อยกว่า ตัวแบ่ง และกลุ่มที่มีข้อมูลน้อยกว่าตัวแบ่ง และอีกกลุ่มจะมีข้อมูลที่มากกว่าตัวแบ่ง ซึ่งเราเรียกตัวแบ่งว่า ตัวหลัก(pivot) ในการเลือกตัวหลักจะมีอิสระในการเลือกข้อมูลตัวใดก็ได้ที่เราต้องการ การเรียงลำดับแบบเร็วเหมาะกับข้อมูลที่มีการเรียกซ้ำ

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

DTS 09-02/09/52

สรุปบทเรียนเรื่อง Graph

กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อนเช่น การวางข่าย งานคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤติ และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น
กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบด้วยกลุ่มของสิ่งสองสิ่งคือ
(1) โหนด (nodes) หรือ เวอร์เทกซ์ (vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (edges)
การเขียนกราฟแสดงโหนดและเส้นเชื่อมความสัมพันธ์ระหว่างโหนดไม่มีรูปแบบที่ตายตัว การลากเส้นความสัมพันธ์เป็นเส้นลักษณะไหนก็ได้ที่สามารถแสดง ความสัมพันธ์ระหว่างโหนดได้ถูกต้อง
กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนดถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่า
กราฟแบบไม่มีทิศทาง (Undirected Graphs)
และถ้ากราฟนั้นมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟนั้นว่า
กราฟแบบมีทิศทาง(Directed Graphs)
บางครั้งเรียกว่า ไดกราฟ (Digraph)ถ้าต้องการอ้างถึงเอ็จแต่ละเส้นสามารถเขียนชื่อเอ็จกำกับไว้ก็ได้
โดยทั่ว ๆ ไปการเขียนกราฟเพื่อแสดงให้เห็นความสัมพันธ์ ของสิ่งที่เราสนใจแทนโหนดด้วย จุด (pointes)
หรือวงกลม (circles)ที่มีชื่อหรือข้อมูลกำกับ เพื่อบอกความแตกต่างของแต่ละโหนดและเอ็จแทนด้วยเส้น
หรือเส้นโค้งเชื่อมต่อระหว่างโหนดสองโหนดถ้าเป็นกราฟแบบมีทิศทางเส้นหรือเส้นโค้งต้อง
มีหัวลูกศรกำกับทิศทางของความสัมพันธ์ด้วย

กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง (empty graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด หรือเชื่อมตัวเอง เอ็จไม่มีทิศทางกำกับ ลำดับของการเชื่อมต่อกันไม่สำคัญ นั่นคือไม่มีโหนดใดเป็นโหนดแรก (first node) หรือไม่มีโหนดเริ่มต้นไม่มีโหนดใดเป็นโหนดสิ้นสุด ดังนั้นเราอาจจะกล่าวว่าเอ็จเชื่อมโหนด u และโหนด v หรือจะกล่าวว่าเอ็จเชื่อมโหนด v และโหนด u ก็มีความหมายเหมือนกัน



ตัวอย่างกราฟแบบไม่มีทิศทางในรูปแบบต่างๆ

ตัวอย่างกราฟแบบไม่มีทิศทางในรูปแบบต่าง ๆ และโหนดสองโหนดในกราฟแบบไม่มีทิศทางถือว่าเป็นโหนดที่ ใกล้กัน (adjacent) ถ้ามีเอ็จเชื่อมจากโหนดที่หนึ่งไปโหนดที่สอง กราฟ (ก) แสดงกราฟที่มีลักษณะ ต่อเนื่อง (connected) เป็นกราฟที่มีเส้นทางเชื่อมจากโหนดใด ๆ ไปยังโหนดอื่นเสมอ โดยมีโหนด 1 กับโหนด 2 และ โหนด 3 กับ โหนด 4 เป็นโหนดที่ใกล้กัน แต่โหนด 1 และ 4 ไม่ใช่โหนดที่ใกล้กัน กราฟ (ข) แสดงกราฟที่มีลักษณะเป็น วีถี (path) มีเส้นทางเชื่อมไปยังโหนดต่าง ๆ อย่างเป็นลำดับ โดยแต่ละโหนดจะเป็นโหนดที่ใกล้กันกับโหนดที่อยู่ถัดไป กราฟ (ค) แสดงกราฟที่เป็นวัฎจักร (cycle) ซึ่งต้องมีอย่างน้อย 3 โหด ที่โหนดสุดท้ายต้องเชื่อมกับโหนดแรก กราฟ (ง) แสดงกราฟที่มีลักษณะ ไม่ต่อเนื่อง (disconnected) เนื่องจากไม่มีเส้นทางเชื่อมจากโหนด 3 ไปยังโหนดอื่นเลย กราฟ (ก), (ข) และ (ค) ถือว่าเป็นกราฟต่อเนื่อง และกราฟ (จ) แสดงกราฟที่เป็นทรี โดยทรีเป็นกราฟที่ต่อเนื่อง ไม่มีทิศทาง และไม่เป็นวัฏจักร

กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง (empty graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด เอ็จมีทิศทางกำกับแสดงลำดับของการเชื่อมต่อกัน โดยมีโหนดเริ่มต้น (source node) และโหนดสิ้นสุด (target node)
รูปแบบต่าง ๆ ของกราฟแบบมีทิศทางเหมือนกับรูปแบบของกราฟ ไม่มีทิศทาง ต่างกันตรงที่กราฟแบบนี้จะมีทิศทางกำกับด้วยเท่านั้น




ตัวอย่างกราฟแบบมีทิศทาง

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

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

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

การท่องไปในกราฟ

การท่องไปในกราฟ (graph traversal) คือ กระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับการท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียว แต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้นเพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำเครื่องหมายมาร์คบิตบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้วเพื่อไม่ให้เข้าไปเยือนอีก สำหรับเทคนิคการท่องไปในกราฟมี 2 แบบดังนี้
การท่องแบบกว้าง (breadth first traversal) วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟ
การท่องแบบลึก (depth first traversal) การทำงานคล้ายกับการท่องทีละระดับของทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น ย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด

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

กราฟเป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบด้วยกลุ่มของสิ่งสองสิ่ง คือ

- โหนด หรือ เวอร์เทกซ์

- เส้นเชื่อมความสัมพันธ์ระหว่างโหนดเรียว่า เอ็จ

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

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