Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Lập Trình

Thuật toán Prim tìm Cây Khung Tối Thiểu


Giới thiệu

Cho một đồ thị liên thông G(V, E) với trọng số (chi phí) cho mọi cạnh. Thuật toán Prim sẽ tìm cây khung tối thiểu (Minimum Spanning Tree - MST) từ đồ thị G.

Đây là phương pháp "phát triển cây". Thuật toán cần một đỉnh gốc (seed vertex) để bắt đầu xây dựng cây. Từ đỉnh gốc này, cây được mở rộng dần dần cho đến khi bao phủ toàn bộ đồ thị.

Thuật toán Prim tìm Cây Khung Tối Thiểu

Bài toán được giải quyết bằng hai tập hợp: một tập chứa các đỉnh đã chọn, tập kia chứa các đỉnh chưa xét. Từ đỉnh gốc, thuật toán lấy các đỉnh kề dựa trên chi phí cạnh nhỏ nhất, từ đó mở rộng cây bằng cách thêm đỉnh lần lượt.

Độ phức tạp thời gian: O(V²), trong đó V là số đỉnh.

Đầu vào và Đầu ra

Đầu vào: Danh sách kề: Thuật toán Prim tìm Cây Khung Tối Thiểu
Đầu ra: (0)---(1|1)  (0)---(2|3)  (0)---(3|4) (1)---(0|1)  (1)---(4|2) (2)---(0|3) (3)---(0|4) (4)---(1|2)  (4)---(5|2) (5)---(4|2)  (5)---(6|3) (6)---(5|3)

Thuật toán

prims(g: Graph, t: tree, start)

Đầu vào: Đồ thị g, một cây rỗng và đỉnh gốc tên là 'start'

Đầu ra: Cây sau khi thêm các cạnh.

Begin
  định nghĩa hai tập hợp usedVert, unusedVert
  usedVert[0] := start và unusedVert[0] := ∅
  với mọi đỉnh trừ start làm:
    usedVert[i] := ∅
    unusedVert[i] := i   // thêm tất cả đỉnh vào danh sách chưa dùng
  done
  trong khi số đỉnh trong usedVert ≠ V làm:  // V là tổng số nút
    min := ∞
    với mọi đỉnh của mảng usedVert làm:
      với mọi đỉnh của đồ thị làm:
        nếu min > cost[i,j] VÀ i ≠ j thì
          min := cost[i,j]
          ed := cạnh giữa i và j, chi phí của ed := min
        done
      done
    done
    unusedVert[đích của ed] := ∅
    thêm cạnh ed vào cây t
    thêm nguồn của ed vào usedVert
  done
End

Ví dụ (C++)

#include <iostream>
#define V 7
#define INF 999
using namespace std;

// Ma trận chi phí của đồ thị
int costMat[V][V] = {
  {0, 1, 3, 4, INF, 5, INF},
  {1, 0, INF, 7, 2, INF, INF},
  {3, INF, 0, INF, 8, INF, INF},
  {4, 7, INF, 0, INF, INF, INF},
  {INF, 2, 8, INF, 0, 2, 4},
  {5, INF, INF, INF, 2, 0, 3},
  {INF, INF, INF, INF, 4, 3, 0}
};

typedef struct {
  int u, v, cost;
} edge;

class Tree {
  int n;
  edge edges[V-1];  // cây có V-1 cạnh
public:
  Tree() { n = 0; }
  void addEdge(edge e) { edges[n] = e; n++; }
  void printEdges() {
    int tCost = 0;
    for(int i = 0; i < n; i++) {
      cout << "Edge: " << char(edges[i].u + 'A') << "--" << char(edges[i].v + 'A');
      cout << " And Cost: " << edges[i].cost << endl;
      tCost += edges[i].cost;
    }
    cout << "Total Cost: " << tCost << endl;
  }
  friend void prims(Tree &tre, int start);
};

void prims(Tree &tr, int start) {
  int usedVert[V], unusedVert[V];
  int i, j, min, p;
  edge ed;
  // Khởi tạo
  usedVert[0] = start; p = 1;
  unusedVert[0] = -1;  // -1 chỉ vị trí trống
  for(i = 1; i < V; i++) {
    usedVert[i] = -1;   // tất cả vị trí trừ đầu tiên đều trống
    unusedVert[i] = i;  // điền các đỉnh
  }
  tr.n = 0;
  // Lấy cạnh và thêm vào cây
  while(p != V) {  // p là số đỉnh trong mảng usedVert
    min = INF;
    for(i = 0; i < p; i++) {
      for(j = 0; j < V; j++) {
        if(unusedVert[j] != -1) {
          if(min > costMat[i][j] && costMat[i][j] != 0) {
            min = costMat[i][j];
            ed.u = i; ed.v = j; ed.cost = min;
          }
        }
      }
    }
    unusedVert[ed.v] = -1;  // xóa v khỏi unusedVertex
    tr.addEdge(ed);
    usedVert[p] = ed.u; p++;  // thêm u vào usedVertex
  }
}

int main() {
  Tree tr;
  prims(tr, 0);  // đỉnh bắt đầu 0
  tr.printEdges();
}

Kết quả đầu ra

(0)---(1|1)  (0)---(2|3)  (0)---(3|4) (1)---(0|1)  (1)---(4|2) (2)---(0|3) (3)---(0|4) (4)---(1|2)  (4)---(5|2) (5)---(4|2)  (5)---(6|3) (6)---(5|3)