Dijkstra's Algorithm example

สำหรับบทความต่อไปนี้จะเป็นการแนะนำในเรื่องของ Dijkstra's Algorithm ซึ่งถูกนำมาใช้ในการหา Shortest Path ใน Graph Structure ระหว่าง Node หนึ่งไปยังอีก Node หนึ่งโดยใช้วิธีการปรับค่าระยะทางที่ดีที่สุดไปเรื่อยๆ ซ้ำไปซ้ำมา จนได้ค่าระยะทางที่ดีที่สุด

ซึ่งในความเป็นจริงแล้ว Dijkstra's Algorithm ไม่ได้ตอบกลับมาเป็น Path ที่สั้นที่สุด แต่จะตอบกลับมาเป็นระยะทางที่สั้นที่สุดเท่านั้น เดี๋ยวลองดู slide อธิบายเกี่ยวกับ Dijkstra's Algorithm กันนะครับ (เป็น clip ที่ผมาเอามาจาก YouTube posted ไว้โดย bactac) ค่อยๆดูไป pause ไปทีละ Slide แล้วพยายามทำความเข้าใจครับ

แหล่งที่มา: http://www.youtube.com/watch?v=UG7VmPWkJmA&feature=related

Graph Implementation

สำหรับบทความนี้ ผมอยากจะมาแนะนำเกี่ยวกับทฤษฎีพื้นฐานเกี่ยวกับ Graph Data Structure ในส่วนของ Graph Implementation ซึ่งจะพูดถึงการนำ Graph ที่อยู่ในชีวิตประจำวัน มาแปลงเป็น Data Structure ในรูปแบบของ Graph สำหรับรูปแบบที่นิยมใช้งานมีอยู่ด้วยกัน 2 แบบ คือ แบบ Adjacency Metrix และแบบ Adjacency List

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

แหล่งที่มา: http://www.youtube.com/watch?feature=endscreen&NR=1&v=2guA5uMEmZQ

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