สรุปการเรียน เรื่อง Summary B4 Final

Tree

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

การท่องไปในไบนารีทรี
ปฏิบัติการที่สำคัญในไบนารีทรี คือ การท่องไปในไบนารีทรี (Traversing Binary Tree) เพื่อเข้าไปเยือนทุก ๆโหนดในทรี ซึ่งวิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุก ๆ โหนด ๆ ละหนึ่งครั้งวิธีการท่องไปนั้นมีด้วยกันหลายแบบแล้วแต่ว่าต้องการลำดับขั้นตอนการเยือนอย่างไร โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N)
ทรีย่อยทางซ้าย (แทนด้วย L) หรือทรีย่อยทางขวา (แทนด้วย R)

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

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

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

การท่องไปในกราฟ มี 2 แบบ คือ
1. การค้นหาแบบกว้าง (Breadth-first Search)
2. การค้นหาแบบลึก (Depth-first Search)

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

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

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

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

การค้นหาแบบไบนารี (Binary Search)
เริ่มการค้นหาแบบไบนารีด้วยการเปรียบเทียบกับค่ากลางในลิสต์ คือค่า a[4] ซึ่งเก็บค่า 8 ซึ่ง 12 > a[4] หมายความว่าค่า 12 ควรจะอยู่ในข้อมูลด้านขวาของ a[4] คือ ช่วง a[5] …a[8]
โดยไม่สนใจช่วงข้อมูล a[1] …a[3] และใช้วิธีการค้นหาแบบไบนารีเช่นเดิมอีกกับชุดข้อมูลครึ่งหลัง คือa[5] …a[8] นั่นคือ เปรียบเทียบกับค่ากลางของชุดข้อมูลครึ่งหลัง(a[5] …a[8] ) คือค่า a[6] ซึ่งเก็บค่า 12 ซึ่ง 12 = a[6] จะได้ว่าค่า 12 อยู่ในตำแหน่งที่ 6 ในลิสต์


DTS 11-16-09-2552

สรุปการเรียน เรื่อง Sorting

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

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


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


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

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

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

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

ข้อมูลเริ่มต้น 12 ตัว
35 67 58 47 22 99 82 43 11 40 29 55
รอบที่ 1 พิจารณาในหลักหน่วย
กลุ่ม 0 40
กลุ่ม 1 11
กลุ่ม 2 22 82
กลุ่ม 3 43
กลุ่ม 4
กลุ่ม 5 35 55
กลุ่ม 6
กลุ่ม 7 67 47
กลุ่ม 8 58


เมื่อจัดกลุ่มในรอบแรกเสร็จแล้วรวบรวมข้อมูลในทุกกลุ่มเริ่มตั้งแต่ข้อมูลในกลุ่ม 0 จนถึงกลุ่ม 9ได้ข้อมูลเรียงตามลำดับดังนี้
40 11 22 82 43 35 55 67 47 58 99 29
รอบที่ 2 พิจารณาในหลักสิบ
กลุ่ม 0
กลุ่ม 1 11
กลุ่ม 2 22 29
กลุ่ม 3 35
กลุ่ม 4 40 43 47
กลุ่ม 5 55 58
กลุ่ม 6 67
กลุ่ม 7
กลุ่ม 8 82
กลุ่ม 9 99
ในรอบที่ 2 เมื่อทำการจัดกลุ่มเรียบร้อยแล้ว
ให้รวบรวมข้อมูลในทุกกลุ่มเริ่มจากข้อมูลในกลุ่ม 0
จนถึงกลุ่ม 9 ได้ข้อมูลเรียงตามลำดับดังนี้
11 22 29 35 40 43 47 55 58 67 82 99

การเรียงลำดับแบบฐานมีวิธีการที่ไม่ซับซ้อน แต่ค่อนข้างใช้เนื้อที่ในหน่วยความจำมาก เนื่อง จากการจัดเรียงแต่ละรอบจะต้องเตรียมเนื้อที่ สำหรับสร้างที่เก็บข้อมูลในแต่ละกลุ่ม

DTS 10-09-09-2552

สรุปการเรียน Lecture 8 เรื่อง Graph

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

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

กราฟแบบไม่มีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง (Empty Graph)แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด หรือเชื่อมตัวเอง เอ็จไม่มีทิศทางกำกับ ลำดับของการเชื่อมต่อกันไม่สำคัญ นั่นคือไม่มีโหนดใดเป็นโหนดแรก (First Node) หรือไม่มีโหนดเริ่มต้น และไม่มีโหนดใดเป็นโหนดสิ้นสุด
โหนดสองโหนดในกราฟแบบไม่มีทิศทางถือว่าเป็นโหนดที่ใกล้กัน (Adjacent) ถ้ามีเอ็จเชื่อมจากโหนดที่หนึ่งไปโหนดที่สอง
กราฟ (ก) แสดงกราฟที่มีลักษณะ ต่อเนื่อง(Connected) เป็นกราฟที่มีเส้นทางเชื่อมจากโหนดใด ๆ ไปยังโหนดอื่นเสมอ
กราฟ (ข) แสดงกราฟที่มีลักษณะเป็น วีถี(Path) มีเส้นทางเชื่อมไปยังโหนดต่าง ๆ อย่างเป็น
ลำดับ โดยแต่ละโหนดจะเป็นโหนดที่ใกล้กันกับโหนดที่อยู่ถัดไป
กราฟ (ค) แสดงกราฟที่เป็นวัฎจักร (Cycle)ซึ่งต้องมีอย่างน้อย 3 โหนด ที่โหนดสุดท้ายต้องเชื่อมกับโหนดแรก
กราฟ (ง) แสดงกราฟที่มีลักษณะ ไม่ต่อเนื่อง(Disconnected) เนื่องจากไม่มีเส้นทางเชื่อมจากโหนด 3 ไปยังโหนดอื่นเลย
กราฟ (จ) แสดงกราฟที่เป็นทรี โดยทรีเป็นกราฟที่ต่อเนื่อง ไม่มีทิศทาง และไม่เป็นวัฏจักร

กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง (Empty Graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด เอ็จมีทิศทางกำกับแสดงลำดับของการเชื่อมต่อกัน โดยมีโหนดเริ่มต้น(Source Node) และ โหนดสิ้นสุด (Target Node)รูปแบบต่าง ๆ ของกราฟแบบมีทิศทางเหมือนกับรูปแบบ ของกราฟไม่มีทิศทาง ต่างกันตรงที่กราฟแบบนี้จะมีทิศทางกำกับด้วยเท่านั้น
การแทนกราฟในหน่วยความจำในการปฏิบัติการกับโครงสร้างกราฟ สิ่งที่ต้องการจัดเก็บ จากกราฟโดยทั่วไปก็คือ เอ็จ ซึ่งเป็นเส้นเชื่อมระหว่างโหนดสองโหนด มีวิธีการ จัดเก็บหลายวิธี วิธีที่ง่ายและตรงไปตรงมาที่สุดคือ การเก็บเอ็จในแถวลำดับ 2 มิติ

วิธีแทนกราฟในความจำหลัก อีกวิธีหนึ่งซึ่งเป็นที่นิยมใช้ กันมากที่สุดคือ การแทนด้วยแอดจาเซนซีเมทริกซ์(Adjacency Matrix) โดยที่ถ้ากราฟ G มีทั้งหมด nโหนด แอดจาเซนซีเมทริกซ์เป็นเมทริกซ์จัตุรัสขนาด n x n สมมติว่าคือเมทริกซ์ M แต่ละ M(i,j) เมื่อ i, j = 1, 2, 3, . . ., n จะมีค่าเป็น 1 ถ้ามีเอ็จเชื่อมความสัมพันธ์ระหว่างโหนด iไปยังโหนด j และมีค่าเป็น 0 ถ้าไม่มีเอ็จเชื่อมความสัมพันธ์จากโหนด i ไปยังโหนด j หรืออาจจะกำหนดด้วย ค่าตรรกะ (Boolean Value) ก็ได้

อาจกล่าวได้ว่า เมทริกซ์ M บอกให้ทราบว่ามีเส้นทางจากโหนดในแถวที่ i ไปยังโหนดในคอลัมน์ที่ j ขนาดหนึ่งจำนวนเส้นทางเมทริกซ์ M2 บอกให้เราทราบว่ามีเส้นทางจากโหนดในแถวที่ i ไปยังโหนดในคอลัมน์ที่ jขนาดสองจำนวนเส้นทาง เมทริกซ์ M3 บอกให้เราทราบว่ามีเส้นทางจากโหนดในแถวที่ iไปยังโหนดในคอลัมน์ที่ j ขนาดสามจำนวนเส้นทาง และสมาชิก ใด ๆ มีค่าดังนี้
- ถ้า Mk ij = 0 จะได้ว่าไม่มีเส้นทางขนาดk จากโหนดในแถวที่ i ไปยังโหนดในคอลัมน์ที่ j
- ถ้า Mk ij = p เมื่อ p เป็นจำนวนเต็มบวก ได้ว่ามีเส้นทางขนาด k จำนวน p
เส้นทาง จากโหนดในแถวที่ i ไปยังโหนดในคอลัมน์ที่ j

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


DTS 09-02-09-2552