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

Giới thiệu

Cho đồ thị liên thông G(V, E) có trọng số cho mỗi cạnh. Thuật toán Kruskal tìm cây khung tối thiểu (MST) bằng cách gộp các cây nhỏ thành cây lớn.

Đây là phương pháp "gộp cây" (merge-tree). Ban đầu mỗi đỉnh là một cây riêng biệt. Thuật toán sắp xếp tất cả cạnh theo chi phí tăng dần, sau đó lấy lần lượt cạnh có chi phí nhỏ nhất. Nếu cạnh đó không tạo chu trình, thêm vào cây; ngược lại bỏ qua.

Độ phức tạp: O(E log E) hoặc O(E log V), với E là số cạnh, V là số đỉnh.

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

Đầu vào: Ma trận kề 
Đầu ra:
Edge: B--A And Cost: 1
Edge: E--B And Cost: 2
Edge: F--E And Cost: 2
Edge: C--A And Cost: 3
Edge: G--F And Cost: 3
Edge: D--A And Cost: 4
Total Cost: 15

Thuật toán

kruskal(g: Graph, t: Tree)

Đầu vào: Đồ thị g và cây rỗng t

Đầu ra: Cây t với các cạnh được chọn

Begin
  tạo tập hợp cho mỗi đỉnh trong đồ thị g
  với mỗi tập hợp đỉnh u làm:
    thêm u vào vertexSet[u]
  done
  sắp xếp danh sách cạnh
  count := 0
  trong khi count <= V - 1 làm:  // cây phải có V-1 cạnh
    ed := edgeList[count]  // lấy cạnh từ danh sách
    nếu đỉnh đầu và đỉnh cuối của ed nằm trong cùng tập hợp thì
      gộp vertexSet[start] và vertexSet[end]
      thêm ed vào cây t
    count := count + 1
  done
End

Ví dụ (C++)

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

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;

void swapping(edge &e1, edge &e2) {
  edge temp = e1; e1 = e2; e2 = temp;
}

class Tree {
  int n; edge edges[V-1];
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;
  }
};

class VSet {
  int n; int set[V];
public:
  VSet() { n = -1; }
  void addVertex(int vert) { set[++n] = vert; }
  int deleteVertex() { return set[n--]; }
  friend int findVertex(VSet *vertSetArr, int vert);
  friend void merge(VSet &set1, VSet &set2);
};

void merge(VSet &set1, VSet &set2) {
  while(set2.n >= 0) set1.addVertex(set2.deleteVertex());
}

int findVertex(VSet *vertSetArr, int vert) {
  for(int i = 0; i < V; i++)
    for(int j = 0; j <= vertSetArr[i].n; j++)
      if(vert == vertSetArr[i].set[j]) return i;
}

int findEdge(edge *edgeList) {
  int count = -1, i, j;
  for(i = 0; i < V; i++)
    for(j = 0; j < i; j++)
      if(costMat[i][j] != INF) {
        count++;
        edgeList[count].u = i;
        edgeList[count].v = j;
        edgeList[count].cost = costMat[i][j];
      }
  return count + 1;
}

void sortEdge(edge *edgeList, int n) {
  int flag = 1, i, j;
  for(i = 0; i < (n-1) && flag; i++) {
    flag = 0;
    for(j = 0; j < (n-i-1); j++)
      if(edgeList[j].cost > edgeList[j+1].cost) {
        swapping(edgeList[j], edgeList[j+1]);
        flag = 1;
      }
  }
}

void kruskal(Tree &tr) {
  int ecount, maxEdge = V*(V-1)/2;
  edge edgeList[maxEdge], ed;
  int uloc, vloc;
  VSet VSetArray[V];
  ecount = findEdge(edgeList);
  for(int i = 0; i < V; i++) VSetArray[i].addVertex(i);
  sortEdge(edgeList, ecount);
  int count = 0;
  while(count <= V-1) {
    ed = edgeList[count];
    uloc = findVertex(VSetArray, ed.u);
    vloc = findVertex(VSetArray, ed.v);
    if(uloc != vloc) {
      merge(VSetArray[uloc], VSetArray[vloc]);
      tr.addEdge(ed);
    }
    count++;
  }
}

int main() {
  Tree tr;
  kruskal(tr);
  tr.printEdges();
}

Kết quả đầu ra

Edge: B--A And Cost: 1
Edge: E--B And Cost: 2
Edge: F--E And Cost: 2
Edge: C--A And Cost: 3
Edge: G--F And Cost: 3
Edge: D--A And Cost: 4
Total Cost: 15