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

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


Cho đồ thị liên thông G(V,E) với trọng số cạnh. Prim tìm cây khung nhỏ nhất từ G.

Cách tiếp cận phát triển cây (growing tree). Cần giá trị hạt giống (seed vertex) để bắt đầu. Đỉnh hạt giống phát triển thành toàn bộ cây.

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

Giải quyết bằng hai tập hợp: tập đỉnh đã chọn và tập chưa xem xét. Từ đỉnh hạt giống, lấy đỉnh kề dựa trên chi phí cạnh nhỏ nhất, phát triển cây bằng cách thêm nút từng cái.

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

Đầu vào − Danh sách kề:


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

Đầ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, cây rỗng, đỉnh hạt giống 'start'. Đầu ra: Cây sau khi thêm cạnh.

Begin
    định nghĩa hai tập usedVert, unusedVert
    usedVert[0] := start và unusedVert[0] := φ
    for all vertices except start do
        usedVert[i] := φ
        unusedVert[i] := i //thêm tất cả đỉnh vào unused
    done
    while số đỉnh trong usedVert ≠ V do
        min := ∞
        for all vertices của usedVert do
            for all vertices của đồ thị do
                if min > cost[i,j] AND i ≠ j then
                    min := cost[i,j]
                    ed := cạnh giữa i và j, chi phí 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 
#define V 7
#define INF 999
using namespace std;
int costMat[V][V] = { ... };
typedef struct{ int u, v, cost; }edge;
class Tree{ ... };
void prims(Tree &tr, int start){ ... }
main(){ Tree tr; prims(tr, 0); tr.printEdges(); }

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