Thuật toán Kruskal (Minimum Spanning Tree - MST)

Cho đồ thị liên thông G(V,E) với trọng số cạnh. Kruskal tìm cây khung nhỏ nhất dùng đồ thị và chi phí.

Cách tiếp cận gộp cây (merge tree). Ban đầu có nhiều cây riêng biệt, thuật toán gộp chúng bằng cách lấy cạnh chi phí nhỏ nhất, tạo thành một cây đơn lẻ.

Tất cả cạnh được liệt kê, sắp xếp theo chi phí. Từ danh sách, lấy cạnh chi phí nhỏ thêm vào cây, kiểm tra có tạo chu trình không, nếu có thì loại bỏ, lấy cạnh tiếp theo.

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

Đầu vào - Ma trận kề:

0 1 3 4 ∞ 5 ∞
1 0 ∞ 7 2 ∞ ∞
3 ∞ 0 ∞ 8 ∞ ∞
4 7 ∞ 0 ∞ ∞ ∞
∞ 2 8 ∞ 0 2 4
5 ∞ ∞ ∞ 2 0 3
∞ ∞ ∞ ∞ 4 3 0

Đầ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, cây rỗng t

Đầu ra − Cây t với các cạnh đã chọn

Begin
    tạo tập hợp cho mỗi đỉnh trong g
    for each tập đỉnh u do
        thêm u vào vertexSet[u]
    done
    sắp xếp danh sách cạnh
    count := 0
    while count <= V – 1 do
        ed := edgeList[count]
        nếu đỉnh đầu và cuối của ed trong cùng tập thì
            gộp vertexSet[đầu] và vertexSet[cuối]
            thêm ed vào cây t
        count := count + 1
    done
End

Ví dụ (C++)

#include 
#define V 7
#define INF 999
using namespace std;
int costMat[V][V] = { ... };
typedef struct{ int u, v, cost; }edge;
void swapping(edge &e1, edge &e2){ ... }
class Tree{ ... };
class VSet{ ... };
void merge(VSet &set1, VSet &set2){ ... }
int findVertex(VSet *vertSetArr, int vert){ ... }
int findEdge(edge *edgeList){ ... }
void sortEdge(edge *edgeList, int n){ ... }
void kruskal(Tree &tr){ ... }
int main(){ Tree tr; kruskal(tr); tr.printEdges(); }

Đầ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