Graph Traversal

Graph เป็น Data Structure ประเภทหนึ่ง ซึ่งประกอบไปด้วย Node (หรือเรียกว่า Vertex) และ Relationship (หรือเรียกว่า Arc) สำหรับบทความนี้ ผมอยากแนะนำเรื่อง Graph Traversal (การ visit แต่ละ Node ใน Graph Structure) ซึ่งที่นิยมใช้งาน มีอยู่ 2 แบบคือ แบบ Depth-First Search (DFS) (ในการ implement มักจะใช้ Stack) และแบบ Breadth-First Search (ในการ implement มักจะใช้ Queue)

สำหรับการ Traversal ในแบบ Depth-First Search จะใช้วิธีการ travel ไปในแต่ละ Branch ของ Tree ทีละ Branch จนจบ แล้วถึงจะ Travel ไปใน Branch ถัดไป ยกตัวอย่างเช่น Tree ของเรามี 2 branch คือ ด้านซ้ายและด้านขวา Depth-First Search อาจจะเริ่ม Travel ใน Branch ฝั่งซ้ายก่อน และจะ Travel จนครบทุก Node ใน Branch ฝั่งซ้าย เมื่อครบแล้วถึงจะไปเริ่ม Travel ต่อใน Branch ฝั่งขวา

สำหรับการ Traversal ในแบบ Breadth-Firsh Search จะใช้วิธีการ travel เป็นแบบลำดับชั้น สมมุติว่าเรามีโครงสร้างแบบ Tree ที่มี 3 ลำดับชั้น คือ Root , Level-1 และ Level-2 การ Traversal ในแบบ Bread-First Search จะ travel ไปทีละลำดับชั้นจบครบทุก Node เมื่อครบแล้วถึงจะเริ่ม Travel ต่อใน Level ถัดไป

สำหรับ video ต่อไปนี้ เป็น video (เอามาจาก YouTube posted ไว้โดย soetamrizky) ที่แนะนำการ implement Graph Traversal ทั้ง 2 รูปแบบ อธิบายสั้นๆ เข้าใจง่าย ใช้เวลาดูไม่นานครับ

แหล่งที่มา:

1. http://en.wikipedia.org/wiki/Graph_traversal
2. http://www.youtube.com/watch?v=or9xlA3YYzo