Minimum Spanning Tree
Minimum Spanning Tree คืออะไร
Minimum Spanning Tree (MST) หรือ ต้นไม้ครอบคลุมขั้นต่ำ เป็นหนึ่งในแนวคิดสำคัญในทฤษฎีกราฟ โดยเฉพาะในกราฟที่มีน้ำหนัก (weighted graph) ที่ไม่มีทิศทาง (undirected graph) MST เป็นต้นไม้ (tree) ที่ครอบคลุมทุกจุด (vertices) ในกราฟ และมีผลรวมน้ำหนักของเส้นเชื่อม (edges) ต่ำที่สุดเมื่อเทียบกับต้นไม้ครอบคลุมอื่น ๆ ที่เป็นไปได้ในกราฟนั้น
จุดประสงค์ของการหา Minimum Spanning Tree
- ลดค่าใช้จ่าย: ใช้ในการหาวิธีการเชื่อมต่อทุ กจุดในกราฟโดยใช้น้ำหนักรวมของเส้นเชื่อมที่น้อยที่สุด ซึ่งสามารถประยุกต์ใช้ได้ในหลายกรณี เช่น การออกแบบเครือข่ายคอมพิวเตอร์, การวางระบบท่อ, การวางสายไฟฟ้า หรือการออกแบบโครงสร้างพื้นฐานอื่น ๆ ที่ต้องการลดต้นทุนในการเชื่อมต่อ
- ประสิทธิภาพในเครือข่าย: ใช้ในการเพิ่มประสิทธิภาพและลดการซ้ำซ้อนในเครือข่าย เช่น ในการสร้างเครือข่ายการสื่อสารที่มีประสิทธิภาพและมีค่าใช้จ่ายต่ำ
- การวิเคราะห์และเพิ่มประสิทธิภาพระบบ: ใช้ในการวิเคราะห์ระบบที่มีอยู่และปรับปรุงประสิทธิภาพ เช่น การหาเส้นทางการขนส่งที่ประหยัดที่สุด หรือการออกแบบเส้นทางการเดินทางที่มีค่าใช้จ่ายต่ำ
ตัวอย่างการประยุกต์ใช้ Minimum Spanning Tree
- การออกแบบเครือข่ายคอมพิวเตอร์ หา MST เพื่อออกแบบเครือข่ายที่เชื่อมโยงเครื่องคอมพิวเตอร์ทั้งหมดด้วยค่าใช้จ่ายต่ำที่สุด
- **การวางระบบท่อหรือสายไฟ **ใช้ MST ในการวางระบบท่อหรือสายไฟเพื่อเชื่อมต่อทุกบ้านในเมืองด้วยค่าใช้จ่ายน้อยที่สุด
- **การวางแผนเส้นทางการขนส่ง **ใช้ MST ในการวางแผนเส้นทางการขนส่งเพื่อหาวิธีที่ประหยัดต้นทุนและมีประสิทธิภาพในการขนส่งสินค้าระหว่างจุดต่าง ๆ
อัลกอริทึมในการหา Minimum Spanning Tree
มีอัลกอริทึมหลัก ๆ ที่ใช้ในการหา MST ดังนี้:
- Kruskal's Algorithm
- เริ่มต้นด้วยการเรียงลำดับเส้นเชื่อมทั้งหมดตามน้ำหนักจากน้อยไปมาก
- เพิ่มเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดเข้าไปในต้นไม้ครอบคลุมโดยไม่ทำให้เกิดวงจร (cycle)
- ทำซ้ ำจนกว่าจะได้เส้นเชื่อมจำนวน 𝑉−1V−1 เส้น (โดยที่ 𝑉V คือจำนวนจุด)
2. Prim's Algorithm
-
เริ่มต้นจากจุดหนึ่งในกราฟ
-
เพิ่มเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดที่เชื่อมกับจุดที่ยังไม่ได้อยู่ในต้นไม้ครอบคลุม
-
ทำซ้ำจนกว่าจะครอบคลุมทุกจุดในกราฟ
Prim's Algorithm
Prim's Algorithm เป็นหนึ่งในอัลกอริทึมที่ใช้ในการหา Minimum Spanning Tree (MST) ของกราฟที่มีน้ำหนัก (weighted graph) และไม่มีทิศทาง (undirected graph) โดยเริ่มจากจุดหนึ่งและขยายต้นไม้ครอบคลุม (spanning tree) ทีละจุดโดยเลือกเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดที่เชื่อมกับจุดที่ยังไม่ได้อยู่ในต้นไม้ครอบคลุม
หลักการทำงานของ Prim's Algorithm
- เลือกจุดเริ่มต้น: เลือกจุดเริ่มต้นใด ๆ ในกราฟและทำเครื่องหมายว่าอยู่ในต้นไม้ครอบคลุมแล้ว
- ค้นหาเส้นเชื่อมที่มีน้ำหนักน้อยที่สุด: ค้นหาเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดที่เชื่อมจากจุดในต้นไม้ครอบคลุมไปยังจุดที่ยังไม่อยู่ในต้นไม้ครอบคลุม
- เพิ่มเส้นเชื่อมในต้นไม้ครอบคลุม: เพิ่มเส้นเชื่อมที่เลือกและทำเครื่องหมายจุดปลายทางว่าอยู่ในต้นไม้ครอบคลุมแล้ว
- ทำซ้ำ: ทำซ้ำขั้นตอนที่ 2 และ 3 จนกว่าจุดทั้งหมดจะถูกรวมอยู่ในต้นไม้ครอบคลุม
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
// Function to find the vertex with minimum key value
int minKey(vector<int> &key, vector<bool> &mstSet, int V) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (!mstSet[v] && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
// Function to print the constructed MST stored in parent[]
void printMST(vector<int> &parent, vector<vector<int>> &graph, int V) {
cout << "Edge \tWeight\n";
for (int i = 1; i < V; i++)
cout << parent[i] << " - " << i << "\t" << graph[i][parent[i]] << " \n";
}
// Function to construct and print MST for a graph represented using adjacency
// matrix
void primMST(vector<vector<int>> &graph, int V) {
vector<int> parent(V); // Array to store constructed MST
vector<int> key(
V, INT_MAX); // Key values used to pick minimum weight edge in cut
vector<bool> mstSet(V, false); // To represent set of vertices included in MST
// Initialize the first vertex's key as 0 so that it is picked as first vertex
key[0] = 0;
parent[0] = -1; // First node is always root of MST
// The MST will have V vertices
for (int count = 0; count < V - 1; count++) {
// Pick the minimum key vertex from the set of vertices not yet included in
// MST
int u = minKey(key, mstSet, V);
// Add the picked vertex to the MST set
mstSet[u] = true;
// Update key value and parent index of the adjacent vertices of the picked
// vertex
for (int v = 0; v < V; v++) {
// graph[u][v] is non-zero only for adjacent vertices
// mstSet[v] is false for vertices not yet included in MST
// Update the key only if graph[u][v] is smaller than key[v]
if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
}
// Print the constructed MST
printMST(parent, graph, V);
}
int main() {
// Define the number of vertices in the graph
int V = 5;
// Define the graph as an adjacency matrix
vector<vector<int>> graph = {
{0, 2, 0, 6, 0}, {2, 0, 3, 8, 5}, {0, 3, 0, 0, 7},
{6, 8, 0, 0, 9}, {0, 5, 7, 9, 0},
};
// Run Prim's Algorithm
primMST(graph, V);
return 0;
}
อธิบายโค้ด
- การตั้งค่าและประกาศตัวแปร:
minKey
เป็นฟังก์ชันที่หา vertex ที่มีค่า key น้อยที่สุดจากกลุ่มที่ยังไม่รวมใน MSTprintMST
เป็นฟังก์ชันที่พิมพ์ผลลัพธ์ของ MST ที่สร้างขึ้นprimMST
เป็นฟังก์ชันห ลักที่ใช้ Prim's Algorithm ในการหาต้นไม้ครอบคลุมขั้นต่ำ
- ฟังก์ชัน
primMST
:- ใช้
vector<int> parent
เพื่อเก็บค่า parent ของแต่ละ vertex ใน MST - ใช้
vector<int> key
เพื่อเก็บค่า key ที่ใช้ในการเลือกเส้นเชื่อมที่มีน้ำหนักน้อยที่สุด - ใช้
vector<bool> mstSet
เพื่อเก็บสถานะของแต่ละ vertex ว่าถูกรวมใน MST หรือไม่
- ใช้
- การวนลูปเพื่อสร้าง MST:
- เลือก vertex ที่มีค่า key น้อยที่สุดที่ยังไม่รวมใน MST
- ทำเครื่องหมาย vertex นั้นว่าอยู่ใน MST แล้ว
- อัปเดตค่า key และ parent ของ vertex ที่เชื่อมกับ vertex ที่เลือก โดยเลือกเส้นเชื่อมที่มีน้ำหนักน้อยที่สุด
- การเรียกใช้งาน:
- กำหนดจำนวน vertex และกราฟในรูปแบบของ adjacency matrix
- เรียกใช้ฟังก์ชัน
primMST
เพื่อหาต้นไม้ครอบคลุมขั้นต่ำและพิมพ์ผลลัพธ์
โดยนี่คือ ภาพ กราฟต้นฉบับ
และนี่คือ MST ที่ได้จาก Prim
Code Complexity ของ Prim's Algorithm
วิเคราะห์ Time Complexity จาก
- Initialization:
- การตั้งค่าค่าเริ่มต้นสำหรับ
key
และmstSet
ใช้เวลา 𝑂(𝑉)O(V) ซึ่ง 𝑉V คือจำนวนจุด (vertices) ในกราฟ - การตั้งค่า
key[0] = 0
และparent[0] = -1
ใช้เวลา 𝑂(1)O(1)
- การตั้งค่าค่าเริ่มต้นสำหรับ
- Finding the Minimum Key Vertex:
- การค้นหา vertex ที่มีค่า key น้อยที่สุดในฟังก์ชัน
minKey
ใช้เวลา 𝑂(𝑉)O(V) ในการวนลูปค้นหาในทุกครั้งของการวนลูปหลัก - เนื่องจากการค้นหานี้จะถูกเรียกใช้ 𝑉−1V−1 ครั้งในลูปหลัก ดังนั้นเวลาที่ใช้รวมคือ 𝑂(𝑉2)O(V2)
- การค้นหา vertex ที่มีค่า key น้อยที่สุดในฟังก์ชัน
- Updating Key and Parent Arrays:
- สำหรับ vertex แต่ละตัวที่ถูกเลือกในลูปหลัก จะมีการอัปเดตค่า key และ parent ของ vertices ที่เชื่อมต่อกับ vertex ที่เลือก
- การอัปเดตนี้ใช้เวลา 𝑂(𝑉)O(V) สำหรับแต่ละ vertex
- เวลาที่ใช้รวมคือ 𝑂(𝑉2)O(V2) เนื่องจากมี 𝑉−1V−1 ครั้งในลูปหลัก
สรุป
สำหรับ Prim's Algorithm ที่ไม่ใช้โครงสร้างข้อมูลขั้นสูงในการปรับปรุงประสิทธิภาพ:
- Time Complexity: 𝑂(𝑉2)O(V2)
- การค้นหา vertex ที่มีค่า key น้อยที่สุดใช้เวลา 𝑂(𝑉)O(V) ในทุกครั้งของการวนลูปหลัก
- การอัปเดตค่า key และ parent ใช้เวลา 𝑂(𝑉)O(V) สำหรับแต่ละ vertex ที่ถูกเลือกในลูปหลัก
Space Complexity
- Space Complexity: 𝑂(𝑉)O(V)
- การใช้พื้นที่สำหรับเก็บค่า
key
และmstSet
ซึ่งมีขนาด 𝑂(𝑉)O(V) - การใช้พื้นที่สำหรับเก็บค่า
parent
ซึ่งมีขนาด 𝑂(𝑉)O(V) - การเก็บข้อมูลกราฟในรูปแบบ adjacency matrix ใช้พื้นที่ 𝑂(𝑉2)O(V2) ซึ่งเป็นพื้นที่หลักที่ใช้
- การใช้พื้นที่สำหรับเก็บค่า