Skip to main content

graph-algorithms

การทำความเข้าใจเกี่ยวกับ Graph Algorithms​

Graph Algorithms คืออัลกอริธึมที่ใช้ในการจัดการและค้นหาข้อมูลในกราฟ (graph) ซึ่งเป็นโครงสร้างข้อมูลที่ประกอบด้วยจุด (vertices หรือ nodes) และเส้นเชื่อมระหว่างจุดเหล่านั้น (edges) กราฟสามารถใช้ในการแสดงความสัมพันธ์ระหว่างวัตถุต่างๆ เช่น การแสดงเครือข่ายสังคม, ระบบการขนส่ง, ระบบคอมพิวเตอร์ และอื่นๆ

1. คำจำกัดความของกราฟ​

  • Vertex (Node): จุดหรือองค์ประกอบของกราฟ
  • Edge: การเชื่อมต่อระหว่างจุดสองจุดในกราฟ
  • Directed Graph: กราฟที่เชื่อมโยงจากจุดหนึ่งไปยังอีกจุดหนึ่งในทิศทางเดียว (มีทิศทาง)
  • Undirected Graph: กราฟที่เชื่อมโยงระหว่างจุดสองจุดในทิศทางที่ไม่จำกัด
  • Weighted Graph: กราฟที่มีการกำหนดน้ำหนัก (weight) หรือค่าให้กับแต่ละขอบ
  • Unweighted Graph: กราฟที่ขอบไม่มีน้ำหนัก
  • Connected Graph: กราฟที่ทุกจุดในกราฟสามารถเชื่อมโยงถึงกันได้
  • Disconnected Graph: กราฟที่มีจุดบางจุดไม่สามารถเชื่อมโยงถึงจุดอื่นๆ ได้

2. ประเภทของ Graph Algorithms​

1. Depth-First Search (DFS)​

DFS คืออัลกอริธึมการค้นหากราฟที่เริ่มต้นจากจุดเริ่มต้น (source node) แล้วไปยังจุดที่ไม่เคยเยี่ยมชมมาก่อน โดยการเลือกเส้นทางที่ลึกที่สุด (downward) ก่อนที่จะกลับขึ้นไปสำรวจเส้นทางอื่นๆ

  • วิธีการทำงาน:
    1. เริ่มต้นที่จุดเริ่มต้น
    2. เยี่ยมชมจุดนั้นและเยี่ยมชมจุดถัดไปตามเส้นเชื่อม (edge)
    3. ถ้ามีจุดที่ยังไม่ได้เยี่ยมชม, เลือกจุดนั้นและทำซ้ำจนกว่าจะไม่สามารถเยี่ยมชมจุดใหม่ได้
    4. หากไม่สามารถไปต่อได้, กลับไปยังจุดก่อนหน้านี้ที่ยังไม่เยี่ยมชม
  • ประโยชน์: ดีในการค้นหาวงจร (cycle detection) และการค้นหาทุกจุดที่เชื่อมโยงถึงกัน
  • Complexity: ( O(V + E) ), โดยที่ ( V ) คือจำนวนจุดและ ( E ) คือจำนวนเส้นเชื่อม

2. Breadth-First Search (BFS)​

BFS คืออัลกอริธึมการค้นหากราฟที่เริ่มต้นจากจุดเริ่มต้นและสำรวจในระดับ (layer) ที่ใกล้ที่สุดก่อน แล้วค่อยๆ ขยายไปยังระดับถัดไป

  • วิธีการทำงาน:
    1. เริ่มต้นจากจุดเริ่มต้น
    2. เยี่ยมชมทุกจุดที่เชื่อมโยงกับจุดเริ่มต้นก่อน
    3. จากนั้น เยี่ยมชมจุดที่เชื่อมโยงกับจุดที่เพิ่งเยี่ยมชม
    4. ทำซ้ำจนกว่าจะเยี่ยมชมทุกจุดที่สามารถเข้าถึงได้
  • ประโยชน์: ดีในการหาทางสั้นที่สุดจากจุดเริ่มต้นไปยังจุดปลาย
  • Complexity: ( O(V + E) )

3. Dijkstra's Algorithm​

Dijkstra's Algorithm เป็นอัลกอริธึมที่ใช้ในการหาค่าทางสั้นที่สุดจากจุดเริ่มต้น (source) ไปยังจุดปลาย (destination) ในกราฟที่มีน้ำหนักของขอบ (edge weights)

  • วิธีการทำงาน:
    1. กำหนดค่าเริ่มต้นให้กับทุกจุดในกราฟ (ระยะทางจากจุดเริ่มต้นเป็นค่ารวมของขอบ)
    2. เริ่มจากจุดเริ่มต้นและคำนวณทางสั้นที่สุดไปยังจุดที่เชื่อมโยงกับจุดเริ่มต้น
    3. อัปเดตระยะทางไปยังจุดที่ไม่เคยเยี่ยมชม
    4. ทำซ้ำกระบวนการจนกว่าจะครบทุกจุด
  • ประโยชน์: ดีในการหาทางสั้นที่สุดในกราฟที่มีค่าเชื่อมต่อเป็นบวก
  • Complexity: ( O(V^2) ) สำหรับกราฟที่ใช้การค้นหาด้วยฟูลล์ และ ( O(V \log V + E) ) สำหรับกราฟที่ใช้ Priority Queue

4. Bellman-Ford Algorithm​

Bellman-Ford Algorithm เป็นอัลกอริธึมที่ใช้สำหรับหาทางสั้นที่สุดจากจุดเริ่มต้นในกราฟที่มีน้ำหนักขอบเป็นลบ

  • วิธีการทำงาน:
    1. เริ่มต้นที่จุดเริ่มต้นและกำหนดระยะทางเริ่มต้นให้เป็นศูนย์
    2. อัปเดตระยะทางจากจุดเริ่มต้นไปยังจุดอื่นๆ โดยการทำซ้ำ ( V-1 ) ครั้ง (V คือจำนวนจุดในกราฟ)
    3. ตรวจสอบว่ามีการปรับปรุงค่าระยะทางในรอบสุดท้ายหรือไม่ ถ้ามีหมายความว่ามีวงจรเชิงลบในกราฟ
  • ประโยชน์: สามารถใช้งานได้กับกราฟที่มีขอบลบ
  • Complexity: ( O(V \times E) )

5. Floyd-Warshall Algorithm​

Floyd-Warshall Algorithm เป็นอัลกอริธึมที่ใช้สำหรับหาทางสั้นที่สุดระหว่างทุกคู่ของจุดในกราฟ (All-pairs shortest path)

  • วิธีการทำงาน:
    1. เริ่มต้นจากการกำหนดระยะทางระหว่างทุกคู่ของจุดเป็นค่าสูงสุด
    2. ทำการอัปเดตค่าระยะทางระหว่างทุกคู่ของจุดโดยการเพิ่มจุดระหว่างกลาง
  • ประโยชน์: ดีในการหาทางสั้นที่สุดระหว่างทุกคู่ของจุด
  • Complexity: ( O(V^3) )

3. Minimum Spanning Tree Algorithms​

การสร้าง Minimum Spanning Tree (MST) คือการค้นหาโครงสร้างของกราฟที่เชื่อมโยงทุกจุดเข้าด้วยกันด้วยค่าใช้จ่ายรวมต่ำที่สุด

1. Kruskal's Algorithm​

Kruskal's Algorithm ใช้ในการหาต้นไม้ที่ครอบคลุมทั้งหมดที่มีค่าน้ำหนักต่ำที่สุด (Minimum Spanning Tree) โดยการเรียงลำดับขอบ (edges) ตามน้ำหนักและเลือกขอบที่ไม่ทำให้เกิดวงจร

  • วิธีการทำงาน:
    1. เรียงลำดับขอบตามน้ำหนัก
    2. เพิ่มขอบที่เชื่อมจุดสองจุดโดยไม่ทำให้เกิดวงจร
  • Complexity: ( O(E \log E) )

2. Prim's Algorithm​

Prim's Algorithm เริ่มจากจุดหนึ่งและเพิ่มขอบที่มีน้ำหนักต่ำที่สุดที่เชื่อมโยงกับจุดที่ยังไม่อยู่ใน MST

  • วิธีการทำงาน:
    1. เริ่มต้นจากจุดหนึ่ง
    2. เลือกขอบที่มีน้ำหนักต่ำที่สุดที่เชื่อมโยงกับจุดใน MST
    3. ทำซ้ำจนกระทั่งทุกจุดในกราฟรวมอยู่ใน MST
  • Complexity: ( O(V^2) ) หรือ ( O(E \log V) ) ถ้าใช้ Priority Queue

4. Topological Sort​

Topological Sort คือการจัดเรียงลำดับจุดในกราฟที่เป็น Directed Acyclic Graph (DAG) โดยให้จุดที่มีการเชื่อมโยงกับจุดอื่นๆ ปรากฏก่อน

  • วิธีการทำงาน: ใช้ DFS หรือ Kahn's Algorithm เพื่อหาลำดับที่ถูกต้อง
  • Complexity: ( O(V + E) )

สรุป​

  • Graph Algorithms ใช้ในการจัดการกับกราฟเพื่อค้นหาคำตอบที่มีประสิทธิภาพในปัญหาต่างๆ เช่น การค้นหาทางสั้นที่สุด, การหาต้นไม้ที่มีค่าน้ำหนักต่ำที่สุด, และการจัดเรียงลำดับจุดในกราฟ
  • DFS และ BFS ใช้ในการค้นหาจุดในกราฟ
  • Dijkstra และ Bellman-Ford ใช้ในการหาทางสั้นที่สุด
  • Kruskal และ Prim ใช้ในการหาต้นไม้ที่มีค่าน้ำหนักต่ำที่สุด
  • Floyd-Warshall ใช้ในการหาทางสั้นที่สุดระหว่างทุกคู่ของจุด