Graph Algorithms

ดร.บุญญฤทธิ์ อุยยานนวาระ
ภาควิชาคอมพิวเตอร์และเทคโนโลยีสารสนเทศ
สถาบันเทคโนโลยีนานาชาติสิรินธร
มหาวิทยาลัยธรรมศาสตร์

 

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

ทีนี้ในบทนี้เราก็มาทำความรู้จักกับเรื่อง กราฟ กันเสียสักหน่อย ก่อนที่เราจะไปดู algorithm เพื่อหา Minimum Spanning Tree กับ Shortest Path ในบทต่อไป

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

Vertex
Edge 
Edge คือทางเชื่อมระหว่าง vertex 2 vertex ซึ่งมักจะแสดงถึงความสัมพันธ์ของทั้งสองเวอร์เท็กนั้น เช่น เส้นทางเดินรถจากเมือง A ไป B หรือ ราคาค่าตั๋วจาก A ไป B เป็นต้น

Directed Edge
คือ edge ที่ระบุทิศทางไว้ด้วย ซึ่ง edge พวกนี้ ใช้ในการแทนข้อมูลที่ระบุทิศทางนั่นเอง เช่น เที่ยวบินจาก จาก A ไป B เป็นต้น (ซึ่งจะเป็น คนละเที่ยวบินจาก B ไป A เป็นต้น)

Undirected edge
edge ที่ไม่ได้ระบุทิศทาง เรียกว่า Undirected edge ซึ่ง edge พวกนี้ ใช้ในการแทนข้อมูลที่ไม่มีทิศทางนั่นเอง เช่น ราคาค่าตั๋วจาก A ไป B เป็นต้น (ซึ่งเป็นราคาเดียวกันกับ ราคาค่าตั๋วจาก B ไป A)

Path
path ทางเดินระหว่าง 2 node (อาจผ่านหลาย node)

Simple Path
คือ Path ที่ไม่มีการเดินไปซ้ำที่ จุดเดิมเลย

Cycle
คือ Path ที่มีจุดเริ่มต้น และ จุดปลายเป็นจุดเดียวกัน 

Simple Cycle
คือ Path ที่ไม่มีการเดินไปซ้ำที่ จุดเดิมเลย (คล้ายๆกับคำว่า simple path แต่มีจุดเริ่มและจุดจบ เป็นจุดเดียวกัน)


Degree ของ Vertex จำนวนของ edge ที่เชื่อมต่ออยู่กับ Vertex นั้น 
Indegree จำนวนของ directed edge ที่วิ่งเข้าสู่ Vertex นั้น 
Outdegree จำนวนของ directed edge ที่วิ่งออกจาก Vertex นั้น 
เรื่องของจำนวนของ edge ที่วิ่งเข้าหรือออกจาก vertex มีความสำคัญในการใช้บอกว่า vertex ไหนมีความสำคัญแค่ไหน เช่น Google ใช้ข้อมูลนี้ในการคำนวน Pagerank เพื่อดูว่าเวลาลิสต์หน้าที่ถูกค้นหาจะเอาหน้าที่สำคัญกว่าออกมาแสดงก่อน เป็นต้น (อ่านเพิ่มเติมได้จากบทความ จุดกำเนิดของกูเกิ้ล)

Complete Graph
Connected Graph
Weighted Graph
Directed Graph
Undierected graph

Subgraph
Spanning tree




การแทนกราฟด้วยข้อมูล (Graph Representation)
Adjacency Matrix



Adjacency List





การค้นหาข้อมูลบนกราฟ (Graph Search)

Depth First Search
Breadth First Search


เดี๋ยวมาเติมข้อมูลให้จ้า.......