Thuật toán Prim tìm cây khung nhỏ nhất trong đồ thị

Posted on by mtoplistChuyên mục:Top List

1. Giới thiệu bài toán:

Bài toán cây khung (cây bao trùm) nhỏ nhất của đồ thị là một trong số những bài toán tối ưu trên đồ thị có nhiều ứng dụng khác nhau trong đời sống. Để minh hoạ thuật toán, chúng ta tham khảo một vài mô hình thực tế tiêu biểu của bài toán:

  • Bài toán xây dựng đường giao thông: giả sử ta muốn xây dựng một hệ thống đường nối n thành phố sao cho giữa các thành phố bất kì luôn có đường đi.Bài toán đặt ra là tim cây khung nhỏ nhất trên đồ thị, mỗi thành phố ứng với một đỉnh sao cho tổng chi phí xây dựng đường đi là nhỏ nhất.
  • Bài toán nối mạng máy tính: Cần nối mạng một hệ thống gồm n máy tính đánhsố từ 1 đến n. Biết chi phí nối máy i với máy j là c[i,j], i,j = 1, 2, . . . ,n ( thôngthường chi phí này phụ thuộc vào độ dài cáp nối cần sử dụng). Hãy tìm cách nối mạng sao cho tổng chi phí nối mạng là nhỏ nhất.

2. Mô tả thuật toán:

  • Ý tưởng: nạp dần các đỉnh vào cây khung. Mỗi lần chọn một đỉnh chưa nạp sao cho đỉnh đó kề và gần nhất với các đỉnh đã nạp.

  • Ví dụ minh hoạ:
    Có đồ thị như hình vẽ, tìm cây bao trùm nhỏ nhất của đồ thị.

    Mô tả thuật toán:
    – Từ đỉnh bắt đầu, lưu đỉnh bắt đầu vào tập các đỉnh đã xét, lưu độ dài từ đỉnh này đến tất cả các đỉnh khác (nếu có đường đi trực tiếp).
    Tập đỉnh đã xét: đỉnh 0

    – Chọn đỉnh gần nhất với tập đỉnh đã xét (đỉnh 2), lưu đỉnh này vào tập các đỉnh đã xét. Cập nhật khoảng cách đến các đỉnh còn lại nếu đỉnh vừa chọn có khoảng cách nhỏ hơn so với khoảng cách đã lưu trước đó.
    Tập đỉnh đã xét: đỉnh 0, đỉnh 2

    – Tiếp tục thực hiện lặp lại bước 2 cho đến khi tìm được cây khung nhỏ nhất.



3. Cài đặt thuật toán (C/C++):

  • Có 2 hàm quan trọng trong thuật toán Prim là hàm đưa ra đỉnh có khoảng cách nhỏ nhất với tập đỉnh đã xét và hàm thực hiện thuật toán Prim.
  • Hàm đưa ra đỉnh có khoảng cách nhỏ nhất với tập đỉnh đã xét: mảng key lưu khoảng cách nhỏ nhất từ cây bao trùm đến các đỉnh
int minKey(int key[], bool mstSet[]) {
       int min = INT_MAX, min_index;
       for (int v = 0; v < V; v++)
         if (mstSet[v] == false && key[v] < min)
             min = key[v], min_index = v;

        return min_index;
     }
  • Hàm thực hiện thuật toán Prim
void primMST(int graph[V][V]) {
       int parent[V]; // Lưu đỉnh cha của đỉnh V trong cây bao trùm nhỏ nhất
       int key[V];   
       bool mstSet[V];  // Đánh dấu các đỉnh đã được thêm vào tập các đỉnh đã xét

   for (int i = 0; i < V; i++)
      key[i] = INT_MAX, mstSet[i] = false;

   key[0] = 0; 
   parent[0] = -1;

   for (int count = 0; count < V-1; count++) {
      int u = minKey(key, mstSet);

      mstSet[u] = true;

    for (int v = 0; v < V; v++)
        if (graph[u][v] && mstSet[v] == false && graph[u][v] <  key[v])
           parent[v]  = u, key[v] = graph[u][v];

    }
 }

Nguồn tham khảo: https://visualgo.net/en/mst

mtoplist