keyboard_tabSkip to content
Mikelopster
Log InRegister
listC++ Data Structure & Algorithm

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 จนกว่าจุดทั้งหมดจะถูกรวมอยู่ในต้นไม้ครอบคลุม
c
#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 คือจำนวนจุด)
c
#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 เพื่อจัดการกับการเชื่อมต่อและการตรวจสอบวงจร
    • เหมาะกับกราฟที่มีการเชื่อมต่อเบาบาง
arrow_backก่อนหน้าShortest partถัดไปLeet codearrow_forward