---
# System prepended metadata

title: Graph Algorithm

---

# 4. Topological Sorting

Topological Sorting คือการจัดลำดับของโหนดในกราฟมีทิศทาง (Directed Graph) ให้เป็นลำดับที่ถ้ามี edge จากโหนด a ไป b แล้ว a จะต้องมาก่อน b ในลำดับนั้น โดย Topological Sorting นั้นอาจมีหลายลำดับที่เป็นไปได้ แต่ละลำดับจะต้องสอดคล้องกับเงื่อนไขของกราฟ

ตัวอย่างเช่น 

![Screen Shot 2568-03-16 at 11.26.54](https://hackmd.io/_uploads/HJfS70m31x.png)

สามารถเรียงให้อยู่ในรูปของ Topological Sorting ได้ดังนี้

![Screen Shot 2568-03-16 at 11.26.58](https://hackmd.io/_uploads/HJLwXAX3Je.png)


## 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$ ตามลำดับ

![Screenshot 2025-03-16 at 21.41.34](https://hackmd.io/_uploads/BJ3XXwNnyx.png)

ตัวอย่างการ union เซต $\{1,4,7\}$ และ $\{2,3,6,8\}$ โปรดสังเกตว่าตัวแทนของเซตที่มีความลึกน้อยกว่า (4) ทำการชี้ไปที่ตัวแทนของเซตที่มีขนาดใหญ่กว่า (2) ซึ่งจะไม่ทำให้ความลึกสูงสุดของกราฟเพิ่มมากขึ้น ในทางกลับกันการชี้ จาก 2 ไป 4 จะทำให้ความลึกสูงสุดเพิ่มขึ้นได้ (4<-2<-3<-6) และ (4<-2<-3<-8)
![Screenshot 2025-03-16 at 21.45.15](https://hackmd.io/_uploads/HJdbEvE2yg.png)

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 โดยปกติอาจมีหลายวิธีในการสร้างต้นไม้ทอดข้าม

ตัวอย่างของกราฟและหนึ่งในต้นไม้ทอดข้าม
![Screenshot 2025-03-16 at 22.12.58](https://hackmd.io/_uploads/HyuF5vV2Jl.png)
![Screenshot 2025-03-16 at 22.13.30](https://hackmd.io/_uploads/HJLsqw4nyx.png)
โดยน้ำหนักของต้นไม้ทอดข้าม คือ ผมรวมของน้ำหนักแต่ละเส้นเชื่อม ในกรณีน้ำหนักมีค่าเท่ากับ $3+5+9+3+2 = 22$

**ต้นไม้ทอดข้ามที่สั้นที่สุด (Minimum Spanning Tree)** คือ ต้นไม้ทอดข้ามที่มีน้ำหนักรวมน้อยที่สุด สำหรับกราฟตัวอย่าง น้ำหนักของ MST คือ 20 และสามารถสร้างต้นไม้ดังนี้
![Screenshot 2025-03-16 at 22.15.57](https://hackmd.io/_uploads/SkjNsvEnyl.png)

**ต้นไม้ทอดข้ามที่ยาวที่สุด (Maximum Spanning Tree)** คือ ต้นไม้ทอดข้ามที่มีน้ำหนักรวมมากที่สุด สำหรับกราฟตัวอย่าง น้ำหนักของ MST คือ 32 และสามารถสร้างต้นไม้ดังนี้
![Screenshot 2025-03-16 at 22.17.47](https://hackmd.io/_uploads/SyuojvV3Jx.png)

สังเกตว่า กราฟหนึ่งอาจมีต้นไม้ทอดข้ามที่สั้นที่สุดและต้นไม้ทอดข้ามที่ยาวที่สุดได้หลายแบบ ดังนั้นต้นไม้เหล่านี้จึงไม่จำเป็นต้องมีเพียงแบบเดียว นอกจากนี้ เราสามารถใช้วิธีการแบบ Greedy ในการสร้างต้นไม้ทอดข้ามที่สั้นที่สุดและยาวที่สุดได้ โดยพิจารณาแต่ละเส้นเชื่อมของกราฟตามลำดับของน้ำหนัก โดยจะเน้นไปที่การหาต้นไม้ทอดข้ามที่สั้นที่สุดเป็นหลัก แต่อัลกอริทึมเหล่านี้สามารถนำไปประยุกต์ใช้กับต้นไม้ทอดข้ามที่ยาวที่สุดได้เช่นกัน

## 6.1 Kruskal’s Algorithm
อัลกอริทึมของ Kruskal เป็นอัลกอริทึมแบบ Greedy สำหรับการหาต้นไม้ทอดข้ามที่สั้นที่สุดของกราฟมีน้ำหนัก มีหลักการสำคัญคือ เริ่มต้นด้วยต้นไม้ที่ประกอบไปด้วยจุดยอดทุกจุด แต่ยังไม่มีเส้นเชื่อมใด ๆ เลย จากนั้นจะเพิ่มเส้นเชื่อมทีละเส้น โดยพิจารณาเส้นเชื่อมจากน้ำหนักน้อยไปหามาก และจะเพิ่มเส้นเชื่อมได้ก็ต่อเมื่อการเพิ่มเส้นเชื่อมนั้นไม่ทำให้เกิดวงจรขึ้นในต้นไม้

อัลกอริทึมนี้รักษา "องค์ประกอบ" หรือ component ของต้นไม้ โดยเริ่มต้นแต่ละจุดยอดจะแยก component กัน เมื่อเพิ่มเส้นเชื่อมใด ๆ ลงไป component ของจุดยอดสองจุดที่เชื่อมต่อด้วยเส้นเชื่อมนั้นจะถูกรวมเข้าด้วยกัน ในที่สุด จุดยอดทั้งหมดจะถูกรวมอยู่ใน component เดียวกัน ซึ่งหมายความว่าได้ต้นไม้ทอดข้ามที่สั้นที่สุดแล้ว

ตัวอย่างและขั้นตอนของ Kruskal
![Screenshot 2025-03-16 at 22.30.07](https://hackmd.io/_uploads/B1LpCD4hke.png)
พิจารณาเส้นเชื่อมจากน้ำหนักน้อยไปมาก
![Screenshot 2025-03-16 at 22.30.14](https://hackmd.io/_uploads/BkLTCw4n1e.png)
![Screenshot 2025-03-16 at 22.30.22](https://hackmd.io/_uploads/HkIpRDEnyg.png)
![Screenshot 2025-03-16 at 22.30.27](https://hackmd.io/_uploads/HyLpRvV3ye.png)
![Screenshot 2025-03-16 at 22.30.33](https://hackmd.io/_uploads/HJL60wVnJx.png)
![Screenshot 2025-03-16 at 22.30.39](https://hackmd.io/_uploads/BJ8aRvEhkx.png)
ซึ่งจะได้ต้นไม้ทอดข้ามที่สั้นที่สุดโดยมีน้ำหนักอยู่ที่ $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**
![Screenshot 2025-03-16 at 23.24.11](https://hackmd.io/_uploads/rJKPj_VnJl.png)
![Screenshot 2025-03-16 at 23.24.19](https://hackmd.io/_uploads/BkYvoON3yg.png)
![Screenshot 2025-03-16 at 23.24.24](https://hackmd.io/_uploads/SJFDouN3yg.png)
![Screenshot 2025-03-16 at 23.24.33](https://hackmd.io/_uploads/SkYDsuNhJg.png)
![Screenshot 2025-03-16 at 23.24.41](https://hackmd.io/_uploads/SkFwjO4nke.png)

**ข้อสังเกต**
- 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 -->