แผนการเรียน
/

Graph Algorithms: MST & Topological Sort
ต้นไม้เชื่อมโยงที่น้อยที่สุดและการเรียงลำดับเชิงทิศทาง

Day 07 Afternoon: การหาเส้นทางที่คุ้มค่าที่สุดและการจัดการลำดับความสัมพันธ์ในกราฟ

สิ่งที่จะได้เรียนรู้

1
Minimum Spanning Tree (MST): อัลกอริทึมของ Kruskal และ Prim
2
โครงสร้างข้อมูลประกอบ: การประยุกต์ใช้ DSU และ Priority Queue ในระดับสูง
3
Topological Sorting: การจัดเรียงโหนดใน Directed Acyclic Graphs (DAG)

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Review: Graph Basics
ทบทวนพื้นฐานของกราฟ

Graph คืออะไร?

V
Vertex (Node) คือ จุดหรือสถานที่ในกราฟ
E
Edge คือ เส้นที่เชื่อมระหว่าง Vertex
W
Weight คือ ค่าต้นทุน เช่น ระยะทาง เวลา หรือค่าใช้จ่าย

Graph เป็นโครงสร้างข้อมูลที่ใช้แทนความสัมพันธ์ระหว่างสิ่งต่าง ๆ

Weighted vs Unweighted Graph
กราฟแบบมีน้ำหนักและไม่มีน้ำหนัก

Unweighted Graph

  • • Edge ไม่มีค่า Weight
  • • ทุกเส้นมีค่าเท่ากัน
  • • ใช้ใน BFS / DFS

Weighted Graph

  • • Edge มีค่า Weight
  • • ใช้แทนต้นทุน เช่น ระยะทาง
  • • ใช้ใน MST และ Shortest Path

MST จะทำงานกับ Weighted Graph

Tree vs Graph
ความแตกต่างระหว่าง Tree และ Graph

1
Graph สามารถมีวงจร (cycle) ได้
2
Tree เป็น Graph แบบพิเศษที่ไม่มี cycle
3
Tree ที่มี n vertices จะมี n-1 edges

MST คือ Tree ที่สร้างจาก Graph

What is a Spanning Tree?
ต้นไม้ที่เชื่อมทุกโหนด

1
Spanning Tree คือ Tree ที่เชื่อมทุก Vertex ใน Graph
2
ไม่มี cycle
3
มี edges = vertices − 1

Graph หนึ่งอันสามารถมี หลาย Spanning Trees

Why Minimum Spanning Tree?
ทำไมต้องใช้ MST

ตัวอย่างการใช้งานจริง

1
การวางสายอินเทอร์เน็ตให้เชื่อมทุกเมืองโดยใช้สายให้น้อยที่สุด
2
การสร้างถนนที่เชื่อมทุกเมืองด้วยต้นทุนต่ำที่สุด
3
การออกแบบเครือข่ายคอมพิวเตอร์

เป้าหมายของ MST คือ "เชื่อมทุกโหนดด้วยต้นทุนต่ำที่สุด"

Spanning Tree Concept
แนวคิดของต้นไม้ที่เชื่อมทุกโหนด

Spanning Tree คือ Tree ที่เชื่อมทุก Vertex ใน Graph โดยไม่มี cycle

A --- B
| \ |
C --- D
  • • ใช้ edges บางส่วนจาก graph
  • • ต้องเชื่อมทุก vertex
  • • ไม่มีวงจร (cycle)

Example Graph
ตัวอย่างกราฟแบบมีน้ำหนัก

A ---4--- B
| |
2 5
| |
C ---3--- D

Graph นี้มีหลายวิธีในการเลือก edges เพื่อสร้าง Spanning Tree

Possible Spanning Trees
Spanning Tree ที่เป็นไปได้

Tree 1

A --- B
|
C --- D

Weight = 4 + 2 + 3 = 9

Tree 2

A --- B
| |
C D

Weight = 4 + 2 + 5 = 11

Minimum Spanning Tree
Spanning Tree ที่มีต้นทุนต่ำที่สุด

A B
|
C --- D

เลือก edges:

  • • A - C (2)
  • • C - D (3)
  • • A - B (4)

Total Weight = 9

How Do We Find MST?
เราจะหา MST ได้อย่างไร?

การลองทุก Spanning Tree เป็นไปไม่ได้สำหรับ Graph ขนาดใหญ่

เราจึงใช้ Greedy Algorithms

Kruskal Algorithm

เลือก edge ที่ weight น้อยที่สุดก่อน

Prim Algorithm

สร้าง tree ทีละ node

ต่อไปเราจะเริ่มจาก Kruskal Algorithm

Kruskal Algorithm
แนวคิดแบบ Greedy

Kruskal ใช้แนวคิด Greedy Algorithm

Greedy คือการเลือกตัวเลือกที่ดีที่สุดในแต่ละขั้น

โดยหวังว่าจะได้ผลลัพธ์ที่ดีที่สุดในภาพรวม

เลือก edge ที่ weight น้อยที่สุดก่อน

Kruskal Algorithm Concept
แนวคิดของ Kruskal

  • 1️⃣ เรียง edges ตาม weight จากน้อยไปมาก
  • 2️⃣ เลือก edge ที่ยังไม่ทำให้เกิด cycle
  • 3️⃣ เพิ่ม edge เข้าไปใน MST
  • 4️⃣ ทำจนได้ edges = V - 1
ผลลัพธ์คือ Minimum Spanning Tree

Example Graph
กราฟตัวอย่าง

A ---4--- B
| |
2 5
| |
C ---3--- D

Edges:

(A,C,2) (C,D,3) (A,B,4) (B,D,5)

Step 1: Sort Edges
เรียง edges ตามน้ำหนัก

(A,C) = 2

(C,D) = 3

(A,B) = 4

(B,D) = 5

เราจะเลือก edge จากบนลงล่าง

Building the MST
สร้าง MST ทีละขั้น

Step 1: เลือก (A,C) weight = 2

Step 2: เลือก (C,D) weight = 3

Step 3: เลือก (A,B) weight = 4

ตอนนี้มี edges = 3 = V-1

ได้ Minimum Spanning Tree แล้ว

Why Do We Need DSU?
ทำไมต้องใช้ Union-Find

เมื่อเพิ่ม edge เราต้องตรวจสอบว่า

จะเกิด cycle หรือไม่

  • DSU ช่วยตรวจสอบว่า node อยู่ใน set เดียวกันหรือไม่
  • ถ้าอยู่ set เดียวกัน → จะเกิด cycle
  • ถ้าอยู่คนละ set → สามารถเพิ่ม edge ได้

Kruskal Implementation
ตัวอย่างโค้ด C++

vector<Edge> edges; sort(edges.begin(), edges.end()); DSU dsu(n); int mst_cost = 0; for(auto e : edges){ if(dsu.find(e.u) != dsu.find(e.v)){ dsu.unite(e.u, e.v); mst_cost += e.w; } }

ใช้ DSU เพื่อป้องกันการสร้าง cycle

Prim Algorithm
การสร้าง MST แบบขยายต้นไม้

Prim Algorithm เป็นอีกวิธีหนึ่งในการหา

Minimum Spanning Tree

แนวคิดหลัก:

เริ่มจาก node หนึ่ง

แล้วค่อย ๆ เพิ่ม edge ที่มีน้ำหนักน้อยที่สุด

เพื่อขยาย tree ทีละ node

Prim Algorithm Concept
แนวคิดของ Prim

  • 1️⃣ เริ่มจาก vertex ใดก็ได้
  • 2️⃣ ดู edges ที่เชื่อมกับ tree
  • 3️⃣ เลือก edge ที่ weight น้อยที่สุด
  • 4️⃣ เพิ่ม vertex ใหม่เข้า tree
  • 5️⃣ ทำซ้ำจนได้ vertices ครบ

ผลลัพธ์คือ Minimum Spanning Tree

Example Graph
กราฟตัวอย่าง

A ---4--- B
| |
2 5
| |
C ---3--- D

เริ่มต้นที่ Vertex A

Building the MST
Prim Step-by-Step

Start at A

Edges from A:

(A,C) = 2

(A,B) = 4

เลือก (A,C)

Tree: A → C

Continue Expansion
ขยายต้นไม้ต่อ

Current Tree: A, C

Candidate edges:

(A,B) = 4

(C,D) = 3

เลือก (C,D)

Tree: A → C → D

สุดท้ายเพิ่ม (A,B)

MST Complete

Prim Implementation
ตัวอย่างโค้ด C++

priority_queue, vector>, greater>> pq; vector visited(n,false); pq.push({0, start}); int mst_cost = 0; while(!pq.empty()){ auto [w,u] = pq.top(); pq.pop(); if(visited[u]) continue; visited[u] = true; mst_cost += w; for(auto [v,weight] : adj[u]){ if(!visited[v]) pq.push({weight,v}); } }

Prim ใช้ Priority Queue เพื่อเลือก edge ที่เล็กที่สุด

Topological Sort
กราฟแบบมีทิศทาง

Topological Sort ใช้กับ

Directed Graph

A → B → D
↓ ↑
C -----

Edge มีทิศทาง เช่น A → B

Directed Acyclic Graph
DAG

Topological Sort ใช้ได้เฉพาะกับ

Directed Acyclic Graph

Directed → มีทิศทาง

Acyclic → ไม่มี cycle

ถ้ามี cycle จะไม่สามารถ Topological Sort ได้

Topological Ordering
การเรียงลำดับโหนด

A → B → D
A → C → D

Topological Order หนึ่งแบบคือ

A → C → B → D

ทุก edge ต้องชี้ไปข้างหน้า

Indegree Concept
จำนวน edge ที่เข้ามา

A → B → D
A → C → D

A : indegree = 0

B : indegree = 1

C : indegree = 1

D : indegree = 2

เริ่มจาก node ที่ indegree = 0

Kahn Algorithm
วิธี BFS

1️⃣ หา node ที่ indegree = 0

2️⃣ ใส่ node ลงใน queue

3️⃣ ลบ node ออกจาก graph

4️⃣ ลด indegree ของ neighbor

5️⃣ ถ้า indegree = 0 ให้ใส่ queue

6️⃣ ทำจนกว่า queue จะว่าง

Step-by-Step
Topological Sort

Start: A (indegree = 0)

Result: A

Remove A → update indegree

B , C → indegree = 0

Queue = [B , C]

Result: A → B → C → D

Topological Sort
C++ Implementation

queue q; for(int i=0;i

ใช้ Queue + Indegree

Kruskal vs Prim
เปรียบเทียบอัลกอริทึม MST

Kruskal

  • เลือก edge ที่ weight น้อยที่สุด
  • สร้าง MST จาก edges
  • ใช้ DSU ป้องกัน cycle
  • เหมาะกับ sparse graph

Prim

  • เริ่มจาก vertex หนึ่ง
  • ขยาย tree ทีละ node
  • ใช้ Priority Queue
  • เหมาะกับ dense graph

MST vs Topological Sort
ความแตกต่างของปัญหา

Minimum Spanning Tree

  • ใช้กับ Undirected Graph
  • Graph ต้องมี weight
  • เป้าหมายคือ minimize cost
  • Algorithms: Kruskal / Prim

Topological Sort

  • ใช้กับ Directed Graph
  • Graph ต้องเป็น DAG
  • เป้าหมายคือเรียงลำดับ node
  • Algorithm: Kahn / DFS

Graph Algorithm Summary
สรุปอัลกอริทึมที่เรียน

Kruskal

Greedy

Sort edges

Use DSU

Prim

Greedy

Grow MST

Priority Queue

Topological Sort

Directed Graph

DAG only

Use indegree

Common Mistakes
ข้อผิดพลาดที่พบบ่อย

  • ❌ ไม่ตรวจสอบ cycle ใน Kruskal
  • ❌ ลืมใช้ visited ใน Prim
  • ❌ ใช้ Topological Sort กับ graph ที่มี cycle
  • ❌ ไม่ตรวจสอบ indegree ก่อนเริ่ม algorithm

Practice Time
ฝึกแก้ปัญหา Graph

ต่อไปเราจะฝึกเขียนโปรแกรม

1
Graph Construction
2
DSU Problems
3
MST Problems
4
Topological Sort Problems