Skip to main content

Minimum Spanning Tree

Minimum Spanning Tree คืออะไร​

Minimum Spanning Tree (MST) หรือ ต้นไม้ครอบคลุมขั้นต่ำ เป็นหนึ่งในแนวคิดสำคัญในทฤษฎีกราฟ โดยเฉพาะในกราฟที่มีน้ำหนัก (weighted graph) ที่ไม่มีทิศทาง (undirected graph) MST เป็นต้นไม้ (tree) ที่ครอบคลุมทุกจุด (vertices) ในกราฟ และมีผลรวมน้ำหนักของเส้นเชื่อม (edges) ต่ำที่สุดเมื่อเทียบกับต้นไม้ครอบคลุมอื่น ๆ ที่เป็นไปได้ในกราฟนั้น

จุดประสงค์ของการหา Minimum Spanning Tree​

  1. ลดค่าใช้จ่าย: ใช้ในการหาวิธีการเชื่อมต่อทุกจุดในกราฟโดยใช้น้ำหนักรวมของเส้นเชื่อมที่น้อยที่สุด ซึ่งสามารถประยุกต์ใช้ได้ในหลายกรณี เช่น การออกแบบเครือข่ายคอมพิวเตอร์, การวางระบบท่อ, การวางสายไฟฟ้า หรือการออกแบบโครงสร้างพื้นฐานอื่น ๆ ที่ต้องการลดต้นทุนในการเชื่อมต่อ
  2. ประสิทธิภาพในเครือข่าย: ใช้ในการเพิ่มประสิทธิภาพและลดการซ้ำซ้อนในเครือข่าย เช่น ในการสร้างเครือข่ายการสื่อสารที่มีประสิทธิภาพและมีค่าใช้จ่ายต่ำ
  3. การวิเคราะห์และเพิ่มประสิทธิภาพระบบ: ใช้ในการวิเคราะห์ระบบที่มีอยู่และปรับปรุงประสิทธิภาพ เช่น การหาเส้นทางการขนส่งที่ประหยัดที่สุด หรือการออกแบบเส้นทางการเดินทางที่มีค่าใช้จ่ายต่ำ

ตัวอย่างการประยุกต์ใช้ Minimum Spanning Tree

  1. การออกแบบเครือข่ายคอมพิวเตอร์ หา MST เพื่อออกแบบเครือข่ายที่เชื่อมโยงเครื่องคอมพิวเตอร์ทั้งหมดด้วยค่าใช้จ่ายต่ำที่สุด
  2. **การวางระบบท่อหรือสายไฟ **ใช้ MST ในการวางระบบท่อหรือสายไฟเพื่อเชื่อมต่อทุกบ้านในเมืองด้วยค่าใช้จ่ายน้อยที่สุด
  3. **การวางแผนเส้นทางการขนส่ง **ใช้ MST ในการวางแผนเส้นทางการขนส่งเพื่อหาวิธีที่ประหยัดต้นทุนและมีประสิทธิภาพในการขนส่งสินค้าระหว่างจุดต่าง ๆ

อัลกอริทึมในการหา Minimum Spanning Tree​

มีอัลกอริทึมหลัก ๆ ที่ใช้ในการหา MST ดังนี้:

  1. 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

  1. เลือกจุดเริ่มต้น: เลือกจุดเริ่มต้นใด ๆ ในกราฟและทำเครื่องหมายว่าอยู่ในต้นไม้ครอบคลุมแล้ว
  2. ค้นหาเส้นเชื่อมที่มีน้ำหนักน้อยที่สุด: ค้นหาเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดที่เชื่อมจากจุดในต้นไม้ครอบคลุมไปยังจุดที่ยังไม่อยู่ในต้นไม้ครอบคลุม
  3. เพิ่มเส้นเชื่อมในต้นไม้ครอบคลุม: เพิ่มเส้นเชื่อมที่เลือกและทำเครื่องหมายจุดปลายทางว่าอยู่ในต้นไม้ครอบคลุมแล้ว
  4. ทำซ้ำ: ทำซ้ำขั้นตอนที่ 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;
}

อธิบายโค้ด

  1. การตั้งค่าและประกาศตัวแปร:
    • minKey เป็นฟังก์ชันที่หา vertex ที่มีค่า key น้อยที่สุดจากกลุ่มที่ยังไม่รวมใน MST
    • printMST เป็นฟังก์ชันที่พิมพ์ผลลัพธ์ของ MST ที่สร้างขึ้น
    • primMST เป็นฟังก์ชันหลักที่ใช้ Prim's Algorithm ในการหาต้นไม้ครอบคลุมขั้นต่ำ
  2. ฟังก์ชัน primMST:
    • ใช้ vector<int> parent เพื่อเก็บค่า parent ของแต่ละ vertex ใน MST
    • ใช้ vector<int> key เพื่อเก็บค่า key ที่ใช้ในการเลือกเส้นเชื่อมที่มีน้ำหนักน้อยที่สุด
    • ใช้ vector<bool> mstSet เพื่อเก็บสถานะของแต่ละ vertex ว่าถูกรวมใน MST หรือไม่
  3. การวนลูปเพื่อสร้าง MST:
    • เลือก vertex ที่มีค่า key น้อยที่สุดที่ยังไม่รวมใน MST
    • ทำเครื่องหมาย vertex นั้นว่าอยู่ใน MST แล้ว
    • อัปเดตค่า key และ parent ของ vertex ที่เชื่อมกับ vertex ที่เลือก โดยเลือกเส้นเชื่อมที่มีน้ำหนักน้อยที่สุด
  4. การเรียกใช้งาน:
    • กำหนดจำนวน vertex และกราฟในรูปแบบของ adjacency matrix
    • เรียกใช้ฟังก์ชัน primMST เพื่อหาต้นไม้ครอบคลุมขั้นต่ำและพิมพ์ผลลัพธ์

โดยนี่คือ ภาพ กราฟต้นฉบับ
original-prim.webp
และนี่คือ MST ที่ได้จาก Prim
result-prim.webp
Code Complexity ของ Prim's Algorithm
วิเคราะห์ Time Complexity จาก

  1. Initialization:
    • การตั้งค่าค่าเริ่มต้นสำหรับ key และ mstSet ใช้เวลา 𝑂(𝑉)O(V) ซึ่ง 𝑉V คือจำนวนจุด (vertices) ในกราฟ
    • การตั้งค่า key[0] = 0 และ parent[0] = -1 ใช้เวลา 𝑂(1)O(1)
  2. Finding the Minimum Key Vertex:
    • การค้นหา vertex ที่มีค่า key น้อยที่สุดในฟังก์ชัน minKey ใช้เวลา 𝑂(𝑉)O(V) ในการวนลูปค้นหาในทุกครั้งของการวนลูปหลัก
    • เนื่องจากการค้นหานี้จะถูกเรียกใช้ 𝑉−1V−1 ครั้งในลูปหลัก ดังนั้นเวลาที่ใช้รวมคือ 𝑂(𝑉2)O(V2)
  3. 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) ซึ่งเป็นพื้นที่หลักที่ใช้

ปรับปรุง Prim's Algorithm ด้วย Priority Queue​

ในการปรับปรุงประสิทธิภาพของ Prim's Algorithm สามารถใช้ Priority Queue เพื่อปรับปรุงการค้นหา vertex ที่มีค่า key น้อยที่สุด:

  • การใช้ Priority Queue (เช่น Min-Heap) จะลดเวลาในการค้นหา vertex ที่มีค่า key น้อยที่สุดจาก 𝑂(𝑉)O(V) เป็น 𝑂(log⁡𝑉)O(logV)
  • เวลาที่ใช้ในการอัปเดตค่า key ใน Priority Queue จะเป็น 𝑂(log⁡𝑉)O(logV) ต่อการอัปเดตหนึ่งครั้ง

ดังนั้น Time Complexity ของ Prim's Algorithm ที่ใช้ Priority Queue จะเป็น:

  • Time Complexity: 𝑂(𝐸log⁡𝑉)O(ElogV)
    • การเพิ่ม vertex ลงใน Priority Queue ใช้เวลา 𝑂(log⁡𝑉)O(logV)
    • การอัปเดตค่า key ใน Priority Queue ใช้เวลา 𝑂(log⁡𝑉)O(logV)
    • มีการอัปเดตทั้งหมด 𝐸E ครั้ง (จำนวนเส้นเชื่อม)

การใช้ Priority Queue จะทำให้ Prim's Algorithm มีประสิทธิภาพดีขึ้นเมื่อทำงานกับกราฟที่มีจำนวนเส้นเชื่อมมาก (dense graph)

Kruskal's Algorithm​

Kruskal's Algorithm เป็นหนึ่งในอัลกอริทึมที่ใช้ในการหา Minimum Spanning Tree (MST) ของกราฟที่มีน้ำหนัก (weighted graph) และไม่มีทิศทาง (undirected graph) โดยอัลกอริทึมนี้ทำงานโดยการเรียงลำดับเส้นเชื่อมทั้งหมดตามน้ำหนักจากน้อยไปมาก จากนั้นเลือกเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดทีละเส้นเพื่อเพิ่มเข้าไปในต้นไม้ครอบคลุม (spanning tree) โดยต้องมั่นใจว่าเส้นเชื่อมนั้นไม่ทำให้เกิดวงจร (cycle)

หลักการทำงานของ Kruskal's Algorithm​

  1. การเรียงลำดับเส้นเชื่อม:
    • เรียงลำดับเส้นเชื่อมทั้งหมดในกราฟตามน้ำหนักจากน้อยไปมาก
  2. การใช้โครงสร้างข้อมูล Union-Find:
    • ใช้โครงสร้างข้อมูล Union-Find เพื่อเก็บและตรวจสอบส่วนที่เชื่อมต่อกันของกราฟ เพื่อให้แน่ใจว่าเส้นเชื่อมที่เลือกจะไม่ทำให้เกิดวงจร
  3. การเลือกเส้นเชื่อม:
    • เริ่มจากเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดและเพิ่มเข้าไปในต้นไม้ครอบคลุม
    • ทำการรวมส่วนที่เชื่อมต่อกันใน Union-Find
    • ทำซ้ำจนกว่าจะมีเส้นเชื่อมจำนวน 𝑉−1V−1 เส้นในต้นไม้ครอบคลุม (โดยที่ 𝑉V คือจำนวนจุด)
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

// โครงสร้างที่ใช้แทนขอบ (edge) ของกราฟ
struct Edge {
  int src, dest, weight;
};

// โครงสร้างที่ใช้แทนกราฟ
struct Graph {
  int V, E;
  vector<Edge> edges;
};

// โครงสร้างที่ใช้สำหรับ Union-Find
struct Subset {
  int parent;
  int rank;
};

// ฟังก์ชันเปรียบเทียบน้ำหนักของขอบ
bool compareEdges(Edge a, Edge b) { return a.weight < b.weight; }

// ฟังก์ชันหา root ของชุดที่ประกอบด้วย element i
int find(vector<Subset> &subsets, int i) {
  if (subsets[i].parent != i) {
    subsets[i].parent = find(subsets, subsets[i].parent);
  }
  return subsets[i].parent;
}

// ฟังก์ชันรวมชุดสองชุดเข้าด้วยกัน
void unionSubsets(vector<Subset> &subsets, int x, int y) {
  int xroot = find(subsets, x);
  int yroot = find(subsets, y);

  if (subsets[xroot].rank < subsets[yroot].rank) {
    subsets[xroot].parent = yroot;
  } else if (subsets[xroot].rank > subsets[yroot].rank) {
    subsets[yroot].parent = xroot;
  } else {
    subsets[yroot].parent = xroot;
    subsets[xroot].rank++;
  }
}

// ฟังก์ชันหลักที่ใช้ Kruskal's Algorithm ในการหา MST
void kruskalMST(Graph &graph) {
  vector<Edge> result;
  int V = graph.V;
  vector<Subset> subsets(V);

  for (int v = 0; v < V; ++v) {
    subsets[v].parent = v;
    subsets[v].rank = 0;
  }

  sort(graph.edges.begin(), graph.edges.end(), compareEdges);

  for (Edge &edge : graph.edges) {
    int x = find(subsets, edge.src);
    int y = find(subsets, edge.dest);

    if (x != y) {
      result.push_back(edge);
      unionSubsets(subsets, x, y);
    }
  }

  cout << "Following are the edges in the constructed MST\n";
  for (Edge &edge : result) {
    cout << edge.src << " -- " << edge.dest << " == " << edge.weight << endl;
  }
}

int main() {
  int V = 4; // Number of vertices in graph
  int E = 5; // Number of edges in graph

  Graph graph;
  graph.V = V;
  graph.E = E;

  // Adding edges
  graph.edges.push_back({0, 1, 10});
  graph.edges.push_back({0, 2, 6});
  graph.edges.push_back({0, 3, 5});
  graph.edges.push_back({1, 3, 15});
  graph.edges.push_back({2, 3, 4});

  kruskalMST(graph);

  return 0;
}

อธิบายโค้ด​

  1. การกำหนดโครงสร้างข้อมูล:
    • โครงสร้าง Edge ใช้แทนเส้นเชื่อม (edge) ของกราฟ โดยเก็บข้อมูลจุดเริ่มต้น ( src), จุดปลายทาง ( dest) และน้ำหนัก ( weight)
    • โครงสร้าง Graph ใช้แทนกราฟ โดยเก็บจำนวนจุด ( V) และจำนวนเส้นเชื่อม ( E) และรายชื่อของเส้นเชื่อม
    • โครงสร้าง Subset ใช้สำหรับ Union-Find โดยเก็บพ่อ ( parent) และระดับ ( rank) ของแต่ละชุด
  2. ฟังก์ชันสำหรับการจัดการ Union-Find:
    • find ใช้หา root ของชุดที่ประกอบด้วย element i
    • unionSubsets ใช้รวมชุดสองชุดเข้าด้วยกัน โดยใช้การจัดการระดับ ( rank) เพื่อให้การรวมมีประสิทธิภาพมากขึ้น
  3. ฟังก์ชันหลัก kruskalMST:
    • เริ่มต้นโดยการจัดเรียงเส้นเชื่อมตามน้ำหนักจากน้อยไปมาก
    • ใช้ Union-Find ในการตรวจสอบว่าการเพิ่มเส้นเชื่อมจะไม่ทำให้เกิดวงจร
    • เพิ่มเส้นเชื่อมที่ไม่ทำให้เกิดวงจรเข้าไปในผลลัพธ์ (MST)
    • พิมพ์ผลลัพธ์ของเส้นเชื่อมที่เป็นส่วนหนึ่งของ MST

โดยนี่คือ ภาพ กราฟต้นฉบับ
original_uml_kruskal.webp
และนี่คือ MST ที่ได้จาก Kruskal
mst_kruskal.webp
Time Complexity

  1. การเรียงลำดับเส้นเชื่อม:
    • Kruskal's Algorithm เริ่มต้นด้วยการเรียงลำดับเส้นเชื่อมทั้งหมดตามน้ำหนักจากน้อยไปมาก ซึ่งใช้เวลา 𝑂(𝐸log⁡𝐸)O(ElogE) เนื่องจากมีการเรียงลำดับ 𝐸E เส้นเชื่อม
  2. การดำเนินการ Union-Find:
    • การค้นหา (find) root ของชุดและการรวม (union) ชุดสองชุดใช้เวลา 𝑂(log⁡𝑉)O(logV) ต่อการดำเนินการหนึ่งครั้งเมื่อใช้ Union-Find พร้อมกับการบีบอัดเส้นทาง (path compression) และการจัดอันดับ (union by rank)
    • Union-Find ใช้ในการตรวจสอบว่าการเพิ่มเส้นเชื่อมจะทำให้เกิดวงจรหรือไม่ และในการรวมชุด
  3. การประมวลผลเส้นเชื่อม:
    • การวนลูปผ่านเส้นเชื่อมทั้งหมดและดำเนินการ Union-Find จะใช้เวลา 𝑂(𝐸log⁡𝑉)O(ElogV) เนื่องจากทุกเส้นเชื่อมอาจต้องใช้เวลา 𝑂(log⁡𝑉)O(logV) ในการดำเนินการ find และ union

สรุป​

  • Time Complexity: 𝑂(𝐸log⁡𝐸+𝐸log⁡𝑉)O(ElogE+ElogV)
    • เนื่องจาก 𝐸log⁡𝐸ElogE สามารถเขียนเป็น 𝑂(𝐸log⁡𝑉)O(ElogV) ในกรณีทั่วไปที่ 𝐸≤𝑉2E≤V2
    • ดังนั้น Time Complexity โดยรวมจะเป็น 𝑂(𝐸log⁡𝑉)O(ElogV)

Space Complexity

  • Space Complexity: 𝑂(𝑉+𝐸)O(V+E)
    • การเก็บข้อมูลของกราฟในรูปแบบของโครงสร้าง edges ใช้พื้นที่ 𝑂(𝐸)O(E)
    • การเก็บข้อมูลสำหรับ Union-Find ใช้พื้นที่ 𝑂(𝑉)O(V)

การวิเคราะห์รายละเอียด​

  1. Initialization:
    • การกำหนดค่าพื้นฐานในโครงสร้าง Union-Find ใช้เวลา 𝑂(𝑉)O(V)
  2. Edge Sorting:
    • การเรียงลำดับเส้นเชื่อมทั้งหมดใช้เวลา 𝑂(𝐸log⁡𝐸)O(ElogE)
  3. Processing Edges:
    • การประมวลผลเส้นเชื่อมแต่ละเส้นโดยใช้ Union-Find ใช้เวลา 𝑂(𝐸log⁡𝑉)O(ElogV)
    • การดำเนินการ find และ union สำหรับแต่ละเส้นเชื่อมใช้เวลา 𝑂(log⁡𝑉)O(logV)

ความแตกต่างระหว่าง Prim และ Kruskal​

Prim's Algorithm และ Kruskal's Algorithm เป็นสองอัลกอริทึมที่นิยมใช้ในการหา Minimum Spanning Tree (MST) ในกราฟที่มีน้ำหนัก แต่มีหลักการและขั้นตอนที่แตกต่างกันไป ดังนี้คือความแตกต่างหลักระหว่าง Prim's Algorithm และ Kruskal's Algorithm:

หลักการทำงาน​

  1. Prim's Algorithm:
    • เริ่มต้นจากจุดใดจุดหนึ่งในกราฟและค่อย ๆ ขยายต้นไม้ครอบคลุมขั้นต่ำ (MST) โดยเพิ่มเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดที่เชื่อมกับจุดที่ยังไม่ได้อยู่ใน MST
    • การขยายต้นไม้ครอบคลุมขั้นต่ำจะเกิดขึ้นภายในจุดที่เชื่อมกันอยู่แล้ว (ภายในกราฟที่มีการเชื่อมต่อ)
  2. Kruskal's Algorithm:
    • เริ่มต้นด้วยการเรียงลำดับเส้นเชื่อมทั้งหมดตามน้ำหนักจากน้อยไปมาก
    • เพิ่มเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดเข้าไปใน MST โดยไม่ทำให้เกิดวงจร (cycle)
    • การเชื่อมต่อจะเกิดขึ้นระหว่างจุดที่ยังไม่ได้เชื่อมต่อกัน (สามารถเชื่อมระหว่างส่วนของกราฟที่แยกกันได้)

ขั้นตอนการทำงาน​

  1. Prim's Algorithm:
    • เลือกจุดเริ่มต้น
    • ใช้โครงสร้างข้อมูลที่สามารถหาเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดได้อย่างรวดเร็ว เช่น Priority Queue
    • เพิ่มเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดที่เชื่อมกับจุดที่ยังไม่ได้อยู่ใน MST
    • ทำซ้ำจนกว่าจุดทั้งหมดจะถูกรวมอยู่ใน MST
  2. Kruskal's Algorithm:
    • เรียงลำดับเส้นเชื่อมทั้งหมดตามน้ำหนัก
    • ใช้โครงสร้างข้อมูลเช่น Union-Find เพื่อจัดการกับวงจร (cycle) และส่วนที่เชื่อมต่อกันของกราฟ
    • เพิ่มเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดเข้าไปใน MST โดยไม่ทำให้เกิดวงจร
    • ทำซ้ำจนกว่าจะมีเส้นเชื่อมจำนวน 𝑉−1V−1 เส้น (โดยที่ 𝑉V คือจำนวนจุดในกราฟ)

การประยุกต์ใช้และประสิทธิภาพ​

  1. Prim's Algorithm:
    • เหมาะสมกับกราฟที่มีจุดเชื่อมต่อกันอยู่แล้ว (dense graph)
    • มีความซับซ้อนเวลาในการทำงานเป็น 𝑂(𝐸+𝑉log⁡𝑉)O(E+VlogV) โดยใช้ Priority Queue (E คือจำนวนเส้นเชื่อม, V คือจำนวนจุด)
    • ประสิทธิภาพดีในกราฟที่มีการเชื่อมต่อหนาแน่น
  2. Kruskal's Algorithm:
    • เหมาะสมกับกราฟที่มีจุดเชื่อมต่อกันบางส่วน (sparse graph)
    • มีความซับซ้อนเวลาในการทำงานเป็น 𝑂(𝐸log⁡𝐸)O(ElogE) หรือ 𝑂(𝐸log⁡𝑉)O(ElogV) โดยใช้ Union-Find (เนื่องจาก 𝐸log⁡𝐸ElogE จะเท่ากับ 𝐸log⁡𝑉ElogV ในกรณีทั่วไป)
    • ประสิทธิภาพดีในกราฟที่มีการเชื่อมต่อเบาบาง

สรุป​

  • Prim's Algorithm:
    • เริ่มจากจุดใดจุดหนึ่งและขยายต้นไม้ครอบคลุมภายในจุดที่เชื่อมกันอยู่แล้ว
    • ใช้โครงสร้างข้อมูลที่สามารถหาเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดได้อย่างรวดเร็ว
    • เหมาะกับกราฟที่มีการเชื่อมต่อหนาแน่น
  • Kruskal's Algorithm:
    • เริ่มจากเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดและเพิ่มเส้นเชื่อมโดยไม่ทำให้เกิดวงจร
    • ใช้โครงสร้างข้อมูล Union-Find เพื่อจัดการกับการเชื่อมต่อและการตรวจสอบวงจร
    • เหมาะกับกราฟที่มีการเชื่อมต่อเบาบาง