# 4. Topological Sorting
Topological Sorting คือการจัดลำดับของโหนดในกราฟมีทิศทาง (Directed Graph) ให้เป็นลำดับที่ถ้ามี edge จากโหนด a ไป b แล้ว a จะต้องมาก่อน b ในลำดับนั้น โดย Topological Sorting นั้นอาจมีหลายลำดับที่เป็นไปได้ แต่ละลำดับจะต้องสอดคล้องกับเงื่อนไขของกราฟ
ตัวอย่างเช่น
สามารถเรียงให้อยู่ในรูปของ Topological Sorting ได้ดังนี้
## 4.1 Kahn's Algorithm
**นิยาม In-degree:**
เรานิยาม in-degree ของโหนดว่าเป็นจำนวน edge ที่เข้ามาในโหนดนั้น กล่าวคือ จำนวนงานที่ต้องทำก่อนที่โหนดนั้นจะสามารถดำเนินการได้ โดยโหนดที่มี in-degree = 0 หมายความว่าสามารถทำงานได้ทันทีเพราะไม่ต้องขึ้นอยู่กับงานอื่น
**กระบวนการของ Kahn's Algorithm**
- คำนวณ in-degree ของแต่ละโหนด
- นำโหนดที่มี in-degree = 0 ใส่ลงในคิว (queue)
- ทำการดึงโหนดจากคิวทีละตัวและนำโหนดนั้นไปใส่ในลำดับ Topological Order
- เมื่อทำการดึงออกจากคิวแล้ว ให้ลดค่า in-degree ของเพื่อนบ้าน (ทุกโหนดที่โหนดที่ดึงออกส่ง edge ไปยังพวกเขา) ทีละ 1
- หาก in-degree ของเพื่อนบ้านใด ๆ ลดลงจนเท่ากับ 0 ให้เพิ่มโหนดนั้นลงในคิว
- ทำซ้ำขั้นตอนที่ 3 จนกว่าคิวจะว่าง
- หากลำดับที่ได้มีจำนวนโหนดเท่ากับจำนวนโหนดในกราฟ แสดงว่าได้ Topological Order ที่ถูกต้อง แต่หากลำดับที่ได้มีจำนวนโหนดน้อยกว่าแสดงว่ากราฟมี cycle และไม่สามารถหาลำดับได้
**ตัวอย่างโปรแกรม**
```cpp=
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 100005; // สมมุติว่า N คือจำนวนโหนดสูงสุด
vector<int> G[N]; // เก็บกราฟในรูปแบบ adjacency list
int indeg[N]; // เก็บค่า in-degree ของแต่ละโหนด
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m; // รับจำนวนโหนดและจำนวน edge
// รับข้อมูลกราฟ: สำหรับทุก edge (u, v) ให้นับ in-degree ของ v
for (int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
G[u].push_back(v);
indeg[v]++;
}
// นำโหนดที่มี in-degree = 0 ใส่ในคิว
queue<int> Q;
for (int u = 1; u <= n; u++){
if (indeg[u] == 0)
Q.push(u);
}
vector<int> seq; // ลำดับ Topological Order
// ทำ Kahn's Algorithm
while (!Q.empty()){
int u = Q.front();
Q.pop();
seq.push_back(u);
// สำหรับทุกโหนดที่ u ส่ง edge ไปยัง v
for (int v : G[u]){
indeg[v]--; // ลด in-degree ของ v ลง 1
if (indeg[v] == 0) // ถ้า in-degree ของ v เท่ากับ 0 ให้เพิ่มลงในคิว
Q.push(v);
}
}
// ตรวจสอบว่าได้ Topological Order ครบทุกโหนดหรือไม่
if (seq.size() != n){
cout << "กราฟมี cycle ไม่สามารถหาลำดับ Topological ได้\n";
} else {
// แสดงลำดับ Topological Order
for (int u : seq)
cout << u << " ";
cout << "\n";
}
return 0;
}
```
## 4.2 การใช้การตรวจจับ Cycle ใน DAG ด้วย DFS
การตรวจจับ cycle ในกราฟที่มีทิศทางด้วย DFS จำเป็นต้องใช้ตัวแปรสีแทนการใช้แค่ visited array เนื่องจากปัญหาการประมวลผลที่เกิดจากการเยี่ยมชมในรอบของ DFS ที่ต่างกัน โดยจะกำหนดสถานะของแต่ละโหนดด้วยสีดังนี้:
- สีขาว (color 0): โหนดยังไม่ได้ถูกเยี่ยมชมเลย
- สีเทา (color 1): โหนดถูกเยี่ยมชมแล้วและกำลังอยู่ในกระบวนการ DFS (อยู่ใน recursion stack)
- สีดำ (color 2): โหนดถูกเยี่ยมชมแล้วและได้ทำการประมวลผลลูกของมันครบถ้วนแล้ว
**กระบวนการทำงาน**
- ในตอนแรก ทุกโหนดจะถูกกำหนดเป็นสีขาว (ค่าเริ่มต้นเป็น 0)
- เมื่อเริ่มต้น DFS จากโหนดหนึ่ง เราจะเปลี่ยนสถานะของโหนดนั้นเป็นสีเทา (1) เพื่อบอกว่าโหนดนั้นกำลังอยู่ในกระบวนการ DFS
- จากนั้นจะทำการเยี่ยมชมโหนดที่ติดกัน ถ้าเจอโหนดใดที่อยู่ในสถานะสีเทา (gray) หมายความว่าโหนดนั้นกำลังอยู่ใน stack อยู่แล้ว นั่นคือเราได้พบ cycle
- หลังจากเยี่ยมชมและประมวลผลลูกของโหนดครบแล้ว เราจะเปลี่ยนสถานะของโหนดนั้นเป็นสีดำ (2) เพื่อบ่งบอกว่าโหนดนั้นได้รับการประมวลผลอย่างสมบูรณ์แล้ว
- ถ้าไม่มี cycle เราสามารถสร้าง topological sort ได้โดยเพิ่มโหนดลงในลิสต์ทันทีที่โหนดเปลี่ยนเป็นสถานะ 2 จากนั้นการกลับลำดับลิสต์ (reverse) จะได้ topological order
**ตัวอย่างโปรแกรม**
```cpp=
const int N = 1001;
int color[N]; // 0 = สีขาว (ยังไม่ประมวลผล), 1 = สีเทา (กำลังประมวลผล), 2 = สีดำ (ประมวลผลเสร็จแล้ว)
vector<int> topo; // สำหรับเก็บลำดับของโหนด เมื่อ DFS เสร็จสิ้น (ลำดับนี้ในแบบย้อนกลับจะเป็น Topological Order)
// สมมุติว่า G เป็น vector<int> G[N] ที่เก็บกราฟแบบ directed
// ฟังก์ชัน DFS สำหรับ Topological Sorting และตรวจจับ cycle
// คืนค่า true ถ้าพบ cycle, false ถ้าไม่พบ
bool dfs(int u) {
// ถ้าโหนด u อยู่ในสถานะสีเทา (กำลังอยู่ใน recursion stack) แสดงว่าพบ cycle แล้ว
if (color[u] == 1)
return true;
// ถ้าโหนด u อยู่ในสถานะสีดำ (ประมวลผลเสร็จแล้ว) ก็ไม่ต้องประมวลผลซ้ำ
if (color[u] == 2)
return false;
// เปลี่ยนสถานะของ u เป็นสีเทา เพื่อบอกว่า DFS จาก u ได้เริ่มต้นแล้ว
color[u] = 1;
// เยี่ยมชมทุกโหนดที่ u มี edge ไปถึง
for (int v : G[u]) {
if (dfs(v))
return true; // หากพบ cycle ให้คืนค่า true ทันที
}
// เมื่อ DFS ของโหนด u เสร็จสิ้น (เยี่ยมชมลูกทั้งหมดแล้ว)
color[u] = 2;
// เพิ่ม u ลงในลำดับผลลัพธ์ เมื่อประมวลผลครบแล้ว
topo.push_back(u);
return false;
}
int main() {
// สมมุติว่า n คือจำนวนโหนดในกราฟ
int n;
cin >> n;
// กำหนดกราฟ G เป็น vector<int> G[N] (โค้ดนี้สมมุติว่ามีอยู่แล้ว)
// ...
// เริ่ม DFS จากทุกโหนดที่ยังไม่ได้ประมวลผล (สีขาว)
bool cycleFound = false;
for (int u = 1; u <= n; ++u) {
if (color[u] == 0) {
if (dfs(u)) {
cout << "พบ cycle" << "\n";
cycleFound = true;
break;
}
}
}
// หากไม่พบ cycle ให้สร้าง Topological Order โดยการกลับลำดับผลลัพธ์
if (!cycleFound) {
reverse(topo.begin(), topo.end());
// แสดงลำดับ Topological Sort
for (int u : topo)
cout << u << " ";
cout << "\n";
}
return 0;
}
```
**ข้อสังเกต**
- วิธีการของ Kahn พิจารณาจุดยอดจากจุดเริ่มต้นในขณะที่ การตรวจสอบวงจรพิจารณาจากปลายทาง
- ทั้ง 2 วิธีการใช้ Adjacency List เพื่อความสะดวกในการค้นหาเพื่อนบ้าน
- ทั้ง 2 วิธีการใช้การวนทุกจุดยอดและจุดเชื่อมทำให้มีค่า $O(n+m)$
### ตัวอย่างโจทย์
- top_sort https://leetcode.com/problems/course-schedule/description/
- top_sort https://leetcode.com/problems/course-schedule-ii/description/
- top_sort https://leetcode.com/problems/loud-and-rich/description/?envType=problem-list-v2&envId=topological-sort
# 5. Union-find Disjoint Set
Union-Find Disjoint Set (DSU) ใช้สำหรับจัดการเชตของเชต (sets of sets) โดยสมาชิกแต่ละตัวจะอยู่ในเซตใดเซตหนึ่งเท่านั้น ในแต่ละเชตจะมีตัวแทนหนึ่งตัว โดยสมาชิกตัวอื่น ๆ จะชี้ไปยังตัวแทน การดำเนินการหลักมีสองอย่างคือ
- find (หรือ root): หาตัวแทนของชุดที่สมาชิกนั้นอยู่ อาจมีการใช้ Path Compression เพื่อทำให้การค้นหาสั้นลง
- union (หรือ merge): รวมชุดสองชุดเข้าด้วยกันโดยเลือกให้ตัวแทนของชุดที่มีขนาดเล็กชี้ไปยังตัวแทนของชุดที่มีขนาดใหญ่กว่าเพื่อไม่ทำให้ขนาดโดยรวมใหญ่ขึ้น
- เทคนิคนี้ทำให้ความยาวของ chain อยู่ในระดับ O(logn) และการดำเนินการใน DSU มีเวลา amortized O(α(n)) โดย α(n) เป็นฟังก์ชัน Inverse Ackermann ที่เติบโตช้ามาก
**กระบวนการ**
- กำหนดให้แต่ละสมาชิกอยู่ในเซตของตัวเองด้วยการเซ็ต `parent[i]=i` และ `sizeArr[i]=1`
- ฟังก์ชัน find:
- เมื่อเรียก find(u), ถ้า parent[u] ไม่เท่ากับ u แสดงว่า u ไม่ใช่ตัวแทน
- เราจะเรียก find(parent[u]) ซ้ำเพื่อค้นหาตัวแทนของ u และปรับ parent[u] ให้ชี้ไปยังตัวแทนโดยตรง (Path Compression)
- ฟังก์ชัน unionSets:
- ก่อนรวม เราจะหาตัวแทนของ u และ v ด้วย find(u) และ find(v)
- ถ้า u และ v อยู่ในชุดเดียวกัน (ตัวแทนเป็นตัวเดียวกัน) ไม่ต้องดำเนินการเพิ่มเติม
- หากไม่เท่ากันให้ตัวแทนของเซตที่มีขนาดเล็กกว่าชี้ไปยังตัวแทนที่มีขนาดใหญ่กว่า อย่าลืมเพิ่มขนาดของเซตที่ใหญ่กว่าตามขนาดของเว๖ที่เล้กกว่าด้วย
ตัวอย่าง DSU 3 เซต ซึ่งประกอบไปด้วย $\{1,4,7\}$, $\{5\}$ และ $\{2,3,6,8\}$ โดยตัวแทนของกลุ่มได้แก่ $4$, $5$ และ $2$ ตามลำดับ
ตัวอย่างการ union เซต $\{1,4,7\}$ และ $\{2,3,6,8\}$ โปรดสังเกตว่าตัวแทนของเซตที่มีความลึกน้อยกว่า (4) ทำการชี้ไปที่ตัวแทนของเซตที่มีขนาดใหญ่กว่า (2) ซึ่งจะไม่ทำให้ความลึกสูงสุดของกราฟเพิ่มมากขึ้น ในทางกลับกันการชี้ จาก 2 ไป 4 จะทำให้ความลึกสูงสุดเพิ่มขึ้นได้ (4<-2<-3<-6) และ (4<-2<-3<-8)
https://visualgo.net/en/ufds
**ตัวอย่างโปรแกรม**
```cpp=
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100005;
// อาร์เรย์ parent เก็บตัวชี้ของแต่ละองค์ประกอบ
int parent[MAXN];
// อาร์เรย์ size เก็บขนาด (จำนวนองค์ประกอบ) ของชุดที่องค์ประกอบนั้นเป็นตัวแทน
int sizeArr[MAXN];
// ฟังก์ชัน find เพื่อค้นหาตัวแทนขององค์ประกอบ u ด้วยเทคนิค Path Compression
int find(int u) {
if (parent[u] != u)
parent[u] = find(parent[u]); // ทำ Path Compression: ให้ทุกองค์ประกอบใน chain ชี้ไปยังตัวแทนโดยตรง
return parent[u];
}
// ฟังก์ชัน union (merge) สำหรับรวมชุดขององค์ประกอบ u และ v โดยใช้ Union by Size
void unionSets(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return; // ถ้าอยู่ในชุดเดียวกันแล้ว ไม่ต้องรวม
// รวมชุดที่มีขนาดน้อยกว่าเข้ากับชุดที่มีขนาดมากกว่า
if (sizeArr[u] < sizeArr[v]) {
parent[u] = v;
sizeArr[v] += sizeArr[u];
} else {
parent[v] = u;
sizeArr[u] += sizeArr[v];
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
// n: จำนวนองค์ประกอบ (หรือ node) ที่จะจัดการ
// m: จำนวน union operations (หรือ edge ที่จะรวมชุด)
// เริ่มต้น: ให้ทุกองค์ประกอบเป็นชุดของตัวเอง
for (int i = 1; i <= n; i++){
parent[i] = i;
sizeArr[i] = 1; // ขนาดเริ่มต้นของชุดคือ 1
}
// รับข้อมูล union operations
for (int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
unionSets(u, v);
}
// ตัวอย่างทดสอบ: ตรวจสอบว่าองค์ประกอบสองตัวอยู่ในชุดเดียวกันหรือไม่
int q;
cin >> q; // จำนวนคำถาม
while (q--) {
int u, v;
cin >> u >> v;
if (find(u) == find(v))
cout << "Yes\n";
else
cout << "No\n";
}
return 0;
}
```
### ตัวอย่างโจทย์
- dsu https://programming.in.th/tasks/1092
- dpu + top_sort https://programming.in.th/tasks/o62_mar_c2_blind
# 6. Minimum Spanning Tree
**ต้นไม้ทอดข้าม (Spanning Tree)** ของกราฟคือการเลือกโหนดทั้งหมดในกราฟและเลือกบาง edge ของกราฟมา โดยที่ต้องมีเส้นทางระหว่างโหนดใด ๆ สองโหนด ในลักษณะที่ต้นไม้ทั่วไปจะต้องเชื่อมต่อกันและไม่มี cycle โดยปกติอาจมีหลายวิธีในการสร้างต้นไม้ทอดข้าม
ตัวอย่างของกราฟและหนึ่งในต้นไม้ทอดข้าม
โดยน้ำหนักของต้นไม้ทอดข้าม คือ ผมรวมของน้ำหนักแต่ละเส้นเชื่อม ในกรณีน้ำหนักมีค่าเท่ากับ $3+5+9+3+2 = 22$
**ต้นไม้ทอดข้ามที่สั้นที่สุด (Minimum Spanning Tree)** คือ ต้นไม้ทอดข้ามที่มีน้ำหนักรวมน้อยที่สุด สำหรับกราฟตัวอย่าง น้ำหนักของ MST คือ 20 และสามารถสร้างต้นไม้ดังนี้
**ต้นไม้ทอดข้ามที่ยาวที่สุด (Maximum Spanning Tree)** คือ ต้นไม้ทอดข้ามที่มีน้ำหนักรวมมากที่สุด สำหรับกราฟตัวอย่าง น้ำหนักของ MST คือ 32 และสามารถสร้างต้นไม้ดังนี้
สังเกตว่า กราฟหนึ่งอาจมีต้นไม้ทอดข้ามที่สั้นที่สุดและต้นไม้ทอดข้ามที่ยาวที่สุดได้หลายแบบ ดังนั้นต้นไม้เหล่านี้จึงไม่จำเป็นต้องมีเพียงแบบเดียว นอกจากนี้ เราสามารถใช้วิธีการแบบ Greedy ในการสร้างต้นไม้ทอดข้ามที่สั้นที่สุดและยาวที่สุดได้ โดยพิจารณาแต่ละเส้นเชื่อมของกราฟตามลำดับของน้ำหนัก โดยจะเน้นไปที่การหาต้นไม้ทอดข้ามที่สั้นที่สุดเป็นหลัก แต่อัลกอริทึมเหล่านี้สามารถนำไปประยุกต์ใช้กับต้นไม้ทอดข้ามที่ยาวที่สุดได้เช่นกัน
## 6.1 Kruskal’s Algorithm
อัลกอริทึมของ Kruskal เป็นอัลกอริทึมแบบ Greedy สำหรับการหาต้นไม้ทอดข้ามที่สั้นที่สุดของกราฟมีน้ำหนัก มีหลักการสำคัญคือ เริ่มต้นด้วยต้นไม้ที่ประกอบไปด้วยจุดยอดทุกจุด แต่ยังไม่มีเส้นเชื่อมใด ๆ เลย จากนั้นจะเพิ่มเส้นเชื่อมทีละเส้น โดยพิจารณาเส้นเชื่อมจากน้ำหนักน้อยไปหามาก และจะเพิ่มเส้นเชื่อมได้ก็ต่อเมื่อการเพิ่มเส้นเชื่อมนั้นไม่ทำให้เกิดวงจรขึ้นในต้นไม้
อัลกอริทึมนี้รักษา "องค์ประกอบ" หรือ component ของต้นไม้ โดยเริ่มต้นแต่ละจุดยอดจะแยก component กัน เมื่อเพิ่มเส้นเชื่อมใด ๆ ลงไป component ของจุดยอดสองจุดที่เชื่อมต่อด้วยเส้นเชื่อมนั้นจะถูกรวมเข้าด้วยกัน ในที่สุด จุดยอดทั้งหมดจะถูกรวมอยู่ใน component เดียวกัน ซึ่งหมายความว่าได้ต้นไม้ทอดข้ามที่สั้นที่สุดแล้ว
ตัวอย่างและขั้นตอนของ Kruskal
พิจารณาเส้นเชื่อมจากน้ำหนักน้อยไปมาก
ซึ่งจะได้ต้นไม้ทอดข้ามที่สั้นที่สุดโดยมีน้ำหนักอยู่ที่ $2+3+3+5+7 = 20$
**กระบวนการ**
- เริ่มต้นจากกราฟที่ประกอบด้วยจุดยอดทั้งหมด แต่ไม่มีเส้นเชื่อมเลย
- เรียงเส้นเชื่อมทั้งหมดตามลำดับน้ำหนักจากน้อยไปหามาก
- พิจารณาเส้นเชื่อมแต่ละเส้นตามลำดับ หากการเพิ่มเส้นเชื่อมนั้นไม่ทำให้เกิดวงจร (cycle) ให้เพิ่มเส้นเชื่อมนั้นเข้าไปในต้นไม้ มิฉะนั้นข้ามเส้นเชื่อมนั้นไป
- ทำซ้ำไปเรื่อย ๆ จนพิจารณาเส้นเชื่อมครบทุกเส้นหรือได้ต้นไม้ทอดข้ามครบแล้ว
**การตรวจสอบการเกิดวงจร**
ปัญหาสำคัญของอัลกอริทึมนี้คือ การตรวจสอบว่าการเพิ่มเส้นเชื่อม (u, v) จะทำให้เกิดวงจรขึ้นในต้นไม้หรือไม่ โดยทั่วไปมีวิธีตรวจสอบได้หลายวิธี เช่น
- ใช้ DFS เพื่อตรวจสอบว่า จุดยอด u และ v อยู่ใน component เดียวกันหรือไม่ หากอยู่แล้วจะเกิด cycle และไม่ควรเพิ่มเส้นเชื่อมนั้น
- ทดลองเพิ่มเส้นเชื่อมนั้นลงไปก่อน แล้วใช้ DFS ตรวจสอบวงจร ถ้าพบว่าเกิดวงจรให้ลบเส้นเชื่อมนั้นออก
- ใช้โครงสร้างข้อมูลที่ชื่อว่า Union-Find Disjoint Set (DSU) เพื่อให้สามารถตรวจสอบได้รวดเร็วว่า จุดยอดทั้งสองอยู่ใน component เดียวกันหรือไม่
โดยทั่วไป DSU เป็นโครงสร้างข้อมูลที่นิยมใช้มากที่สุดในการ implement อัลกอริทึมของ Kruskal เนื่องจากวิธีอื่น ๆ ต้องใช้เวลามากในการทำ Graph Traversal เพื่อเช็คการเกิด cycle
เราสามารถตรวจสอบการเกิดวงจรด้วย DSU ได้ง่าย ๆ โดยการเรียก find(u) และ find(v) ถ้าผลลัพธ์เหมือนกันหมายความว่าจุดยอด u และ v อยู่ใน component เดียวกันแล้ว ห้ามเพิ่มเส้นเชื่อมเข้าไปอีก เพราะจะทำให้เกิดวงจร หากการเพิ่มเส้นเชื่อมไม่ทำให้เกิดวงจรเราจะต้องทำการ union(u, v)
**ข้อสังเกต**
- กราฟถูกเก็บในรูปแบบ Edge list โดยใช้โครงสร้างข้อมูล `vector<Edge> edges;` และ `struct Edge { int u, v, w; };`
- ความซับซ้อนของ Kruskal's Algorithm
- เรียง edge ทั้งหมด: $O(m\log(m))$ โดยที่ m คือจำนวน edge
- ตรวจสอบ Cycle ด้วย DSU (Union-Find): $O(mα(n))$ โดยที่ $α(n)$ คือ Inverse Ackermann function ซึ่งโตช้ามาก)
- รวมทั้งหมดได้เป็น $O(m\log(m))$ + $O(mα(n))$
- https://visualgo.net/en/mst?slide=4
**ตัวอย่างโปรแกรม**
```cpp=
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct Edge {
int u, v, w;
bool operator<(const Edge& other) const {
return w < other.w;
}
};
int parent[MAXN], rnk[MAXN];
// DSU: หาตัวแทนกลุ่มของ node u (Path Compression)
int find(int u) {
if (parent[u] == u)
return u;
return parent[u] = find(parent[u]);
}
// DSU: รวมกลุ่มที่มี node u และ v เข้าด้วยกัน (Union by Rank)
void union_sets(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
if (rnk[u] < rnk[v]) swap(u, v);
parent[v] = u;
if (rnk[u] == rnk[v]) rnk[u]++;
}
int main() {
int n, m; // จำนวน node และ edge
cin >> n >> m;
vector<Edge> edges(m);
for (int i = 0; i < m; i++)
cin >> edges[i].u >> edges[i].v >> edges[i].w;
// 1. จัดเรียง edge จากน้ำหนักน้อยไปมาก
sort(edges.begin(), edges.end());
// 2. กำหนดแต่ละ node ให้เป็นตัวแทนกลุ่มของตัวเอง
for (int i = 1; i <= n; i++)
parent[i] = i, rnk[i] = 0;
int mst_weight = 0; // ผลรวมน้ำหนักของ MST
vector<Edge> mst_edges; // เก็บ edge ที่เลือกไว้ใน MST
// 3. เริ่มเพิ่ม edge เพื่อสร้าง MST
for (auto e : edges) {
if (find(e.u) != find(e.v)) { // ไม่เกิด cycle
union_sets(e.u, e.v); // รวมกลุ่ม
mst_weight += e.w; // รวมผลน้ำหนัก
mst_edges.push_back(e); // เก็บ edge ที่ใช้
}
}
// ตรวจสอบว่ามี MST สมบูรณ์หรือไม่
if (mst_edges.size() != n - 1) {
cout << "ไม่สามารถสร้างต้นไม้ทอดข้ามได้\n";
} else {
cout << "น้ำหนักรวมของต้นไม้ทอดข้ามที่สั้นที่สุด: " << mst_weight << "\n";
cout << "เส้นเชื่อมในต้นไม้:\n";
for (auto e : mst_edges) {
cout << e.u << " - " << e.v << " (weight: " << e.w << ")\n";
}
}
return 0;
}
```
## 6.2 Prim’s Algorithm
Prim's Algorithm เป็นอัลกอริทึม Greedy ที่ใช้สำหรับค้นหาต้นไม้ทอดข้ามที่สั้นที่สุดของกราฟที่มีน้ำหนัก โดยเริ่มต้นจากโหนดใดโหนดหนึ่งก่อนและจะเลือกเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดซึ่งสามารถขยายไปยังโหนดที่ยังไม่อยู่ในต้นไม้ที่สร้างไว้ ทำซ้ำขั้นตอนนี้ไปเรื่อย ๆ จนกระทั่งโหนดทั้งหมดถูกรวมเข้าเป็นส่วนหนึ่งของต้นไม้ทอดข้ามที่สั้นที่สุด หลักการนี้มีความคล้ายคลึงกับอัลกอริทึมของ Dijkstra ซึ่งใช้สำหรับการหาเส้นทางที่สั้นที่สุดจากโหนดเริ่มต้นไปยังโหนดอื่น ๆ แต่มีความแตกต่างตรงที่ Prim จะเลือกเพียงเส้นเชื่อมที่สั้นที่สุดเท่านั้นโดยไม่สนใจเส้นทางสะสม (เพราะฉนั้นถ้าเข้าใจ Disjkstra จะแก้ปัญหา MST ได้ด้วย)
**ตัวอย่างและขั้นตอนของ Prim**
**ข้อสังเกต**
- Prim's Algorithm ที่ใช้ Priority Queue แบบนี้จะมีความซับซ้อนเวลาเป็น $O((m + n) \log (n))$
- เช่นเดียวกับ Diskstra กราฟถูกเก็บในรูปแบบ Adjacency List โดยใช้โครงสร้างข้อมูล `vector<pair<int, int>> G[N]`
- https://visualgo.net/en/mst?slide=5
**กระบวนการ**
- ใช้อาเรย์ dist[u] แทนระยะทางที่สั้นที่สุดของเส้นเชื่อมที่เชื่อมจากต้นไม้ MST ปัจจุบันมายังโหนด u และใช้ Priority Queue ช่วยในการเลือกโหนดที่มีค่า dist[u] น้อยที่สุด
- เริ่มต้นให้ทุกโหนดมีค่า dist เป็น infinity และกำหนดโหนดเริ่มต้นมีค่าเป็น 0
- หยิบโหนดที่มีค่า dist น้อยที่สุดออกจาก Priority Queue มาเพิ่มในต้นไม้ MST
- อัปเดตค่า dist ของโหนดที่เชื่อมต่อกับโหนดที่เพิ่งถูกเลือก แล้วนำกลับเข้า Priority Queue
**ตัวอย่างโปรแกรม**
```cpp=
using pii = pair<int, int>;
vector<int> dist(n+1, INF);
vector<bool> visited(n+1, false);
priority_queue<pii, vector<pii>, greater<pii>> Q;
dist[start] = 0; // กำหนดให้โหนดเริ่มต้นมีระยะ 0
Q.push({dist[start], start}); // ใส่โหนดเริ่มต้นลงในคิว
int sum = 0; // ใช้เก็บผลรวมน้ำหนักของต้นไม้ทอดข้าม
while (!Q.empty()) {
int u = Q.top().second, d = Q.top().first;
Q.pop();
if (visited[u])
continue;
visited[u] = true;
sum += dist[u]; // เพิ่มน้ำหนักของเส้นเชื่อมเข้าสู่ผลรวมของ MST
for (auto vw : G[u]) {
int v = vw.first;
int w = vw.second;
if (!visited[v] && w < dist[v]) {
dist[v] = w; // ปรับน้ำหนักเส้นเชื่อมไปยังโหนด v
Q.push({dist[v], v}); // เพิ่มโหนด v เข้าไปใน Priority Queue ใหม่
}
}
}
// เมื่อเสร็จสิ้น sum จะมีค่าเท่ากับน้ำหนักของ MST
printf("%d\n", sum);
```
### ตัวอย่างโจทย์
- mst - kk - https://programming.in.th/tasks/codecube_121
- mst https://leetcode.com/problems/min-cost-to-connect-all-points/description/
<!-- - dp - tree - https://programming.in.th/tasks/o59_mar_c2_wormholes -->
Sign in with Wallet
Connect another wallet