Thuật toán Prim

NỘI DUNG

Giới thiệu thuật toán Prim

Thuật toán Prim là một thuật toán tìm cây khung nhỏ nhất của một đồ thị có trọng số. Nó bắt đầu từ một đỉnh bất kỳ và mở rộng cây khung theo cách thêm các cạnh với trọng số nhỏ nhất vào cây khung. Thuật toán Prim đảm bảo cho ra kết quả chính xác nhưng có độ phức tạp tính toán khá cao.

Các bước thực hiện thuật toán Prim

Bước 1: Chọn một đỉnh bất kỳ trong đồ thị làm đỉnh bắt đầu.
Bước 2: Tìm cạnh có trọng số nhỏ nhất kết nối đỉnh bắt đầu với một đỉnh khác chưa thuộc cây khung.
Bước 3: Thêm đỉnh mới vào cây khung và lặp lại bước 2 cho các cạnh kết nối đỉnh mới và các đỉnh chưa thuộc cây khung cho đến khi tất cả các đỉnh trong đồ thị đều thuộc cây khung.

Ví dụ về Thuật toán Prim

Chúng ta có đồ thị đơn giản với 4 đỉnh và 5 cạnh, các cạnh được đánh số từ 1 đến 5. Trọng số của mỗi cạnh được cho trong bảng sau:

Cạnh	Đỉnh đầu	Đỉnh cuối	Trọng số
1	A	B	2
2	A	C	1
3	A	D	3
4	B	C	4
5	C	D	5

Bây giờ chúng ta sẽ áp dụng thuật toán Prim để tìm cây khung nhỏ nhất của đồ thị này.

Bước 1: Chọn một đỉnh bất kỳ làm đỉnh bắt đầu, ví dụ chọn đỉnh A.

Bước 2: Tìm cạnh có trọng số nhỏ nhất kết nối đỉnh A với một đỉnh khác chưa thuộc cây khung. Trong trường hợp này, có 3 cạnh kết nối đỉnh A với các đỉnh còn lại:

Cạnh 1 kết nối đỉnh A với đỉnh B với trọng số 2.
Cạnh 2 kết nối đỉnh A với đỉnh C với trọng số 1.
Cạnh 3 kết nối đỉnh A với đỉnh D với trọng số 3.

Vì cạnh 2 có trọng số nhỏ nhất, nên ta thêm cạnh 2 vào cây khung, và đỉnh C trở thành đỉnh mới của cây khung.

Bước 3: Tiếp tục tìm cạnh có trọng số nhỏ nhất kết nối đỉnh trong cây khung với một đỉnh khác chưa thuộc cây khung. Có 3 cạnh kết nối đỉnh trong cây khung với các đỉnh chưa thuộc cây khung:

Cạnh 1 kết nối đỉnh A với đỉnh B với trọng số 2.
Cạnh 4 kết nối đỉnh B với đỉnh C với trọng số 4.
Cạnh 5 kết nối đỉnh C với đỉnh D với trọng số 5.

Vì cạnh 1 có trọng số nhỏ nhất và đỉnh B chưa thuộc cây khung, nên ta thêm cạnh 1 vào cây khung, và đỉnh B trở thành đỉnh mới của cây khung.

Bước 4: Tiếp tục thực hiện bước 3 cho đến khi tất cả các đỉnh trong đồ thị đều thuộc cây khung. Trong trường hợp đồ thị liên thông, bước 4 được thực hiện cho tất cả các đỉnh trong đồ thị. Trong trường hợp đồ thị không liên thông, thuật toán Prim sẽ được thực hiện cho mỗi thành phần liên thông của đồ thị.

Bước 5: Kết thúc thuật toán và trả về cây khung nhỏ nhất của đồ thị.

Cài đặt thuật toán Prim với Python

Đây là mã nguồn Python cho thuật toán Prim sử dụng priority queue (heap) để tìm cây khung nhỏ nhất của đồ thị.

from queue import PriorityQueue

def prim(graph, start):
    # Khởi tạo heap để lưu trữ các cạnh theo thứ tự tăng dần của trọng số
    heap = PriorityQueue()
    
    # Khởi tạo danh sách đỉnh đã thăm và cây khung nhỏ nhất
    visited = set()
    mst = []
    
    # Bắt đầu tìm cây khung nhỏ nhất từ đỉnh bắt đầu
    visited.add(start)
    for dest, cost in graph[start]:
        heap.put((cost, start, dest))
    
    # Tiếp tục tìm kiếm cạnh cho đến khi tất cả các đỉnh đã được thăm
    while not heap.empty():
        cost, source, dest = heap.get()
        
        # Nếu đỉnh đích chưa được thăm, thêm cạnh vào cây khung và đánh dấu đỉnh đã thăm
        if dest not in visited:
            visited.add(dest)
            mst.append((source, dest, cost))
            
            # Thêm các cạnh mới từ đỉnh mới được thêm vào heap để tiếp tục tìm kiếm
            for next_dest, next_cost in graph[dest]:
                if next_dest not in visited:
                    heap.put((next_cost, dest, next_dest))
    
    return mst

Hàm prim nhận đầu vào là đồ thị graph dưới dạng danh sách kề và đỉnh khởi đầu start, và trả về cây khung nhỏ nhất của đồ thị dưới dạng danh sách các cạnh.

Ví dụ sử dụng thuật toán Prim để tìm cây khung nhỏ nhất của đồ thị sau đây:

          5
    0 --------- 1
     |         / |
    6|      /    |7
     |  /        |
     |/          |
    2 --------- 3
          2

Với danh sách kề graph:

graph = {
    0: [(1, 5), (2, 6)],
    1: [(0, 5), (2, 1), (3, 7)],
    2: [(0, 6), (1, 1), (3, 2)],
    3: [(1, 7), (2, 2)],
}

Ta có thể tìm cây khung nhỏ nhất của đồ thị này bằng cách gọi hàm prim(graph, 0):

>>> prim(graph, 0)
[(0, 1, 5), (1, 2, 1), (2, 3, 2)]

Kết quả trả về là danh sách các cạnh của cây khung nhỏ nhất, tức là cạnh (0, 1) với trọng số 5, cạnh (1, 2) với trọng số 2, cạnh (1, 3) với trọng số 6 và cạnh (3, 4) với trọng số 1. Đây là cây khung nhỏ nhất có tổng trọng số là 14.

Kết quả trả về của thuật toán Prim phụ thuộc vào cách thức lưu trữ đồ thị và các tham số truyền vào, nhưng nó sẽ luôn trả về một cây khung nhỏ nhất của đồ thị.

Đánh giá độ phức tạp của thuật toán Prim

Thời gian chạy của thuật toán Prim phụ thuộc vào cách thức lưu trữ đồ thị và cấu trúc dữ liệu được sử dụng để lưu trữ cạnh.
Trong trường hợp tệ nhất, khi sử dụng danh sách kề để lưu trữ đồ thị và sử dụng một mảng 2 chiều để lưu trữ các cạnh, độ phức tạp của thuật toán Prim là O(V^2), trong đó V là số lượng đỉnh của đồ thị.
Tuy nhiên, khi sử dụng priority queue (heap) để lưu trữ các cạnh, độ phức tạp của thuật toán giảm xuống đến O(E log V), trong đó E là số lượng cạnh của đồ thị. Đây là do mỗi lần tìm kiếm cạnh nhỏ nhất cần đưa các cạnh trong heap theo trọng số tăng dần, vì vậy thao tác đưa cạnh vào và lấy cạnh ra khỏi heap có độ phức tạp là O(log E).
Như vậy, trong trường hợp tốt nhất và trung bình, độ phức tạp của thuật toán Prim là O(E log V).

Lập trình Python