Thuật toán DSA Prim

Thuật toán Prim

Thuật toán của Prim tìm Cây bao trùm tối thiểu (MST) trong đồ thị liên thông và vô hướng.

MST được thuật toán Prim tìm thấy là tập hợp các cạnh trong biểu đồ, kết nối tất cả các đỉnh với tổng trọng số cạnh tối thiểu.

Thuật toán của Prim tìm MST bằng cách trước tiên thêm một đỉnh ngẫu nhiên vào MST. Sau đó, thuật toán sẽ tìm đỉnh có trọng số cạnh thấp nhất so với MST hiện tại và đưa đỉnh đó vào MST. Thuật toán của Prim tiếp tục thực hiện việc này cho đến khi tất cả các nút được đưa vào MST.

Thuật toán của Prim rất tham lam và có cách đơn giản để tạo cây bao trùm tối thiểu.

Để thuật toán của Prim hoạt động, tất cả các nút phải được kết nối. Để tìm MST trong đồ thị không liên thông, có thể sử dụng thuật toán Kruskal . Bạn có thể đọc về thuật toán Kruskal ở trang tiếp theo.

Chạy qua thủ công

Chúng ta hãy xem thuật toán của Prim theo cách thủ công trên biểu đồ bên dưới để chúng ta hiểu các thao tác chi tiết từng bước trước khi thử lập trình nó.

Thuật toán của Prim bắt đầu phát triển Cây bao trùm tối thiểu (MST) từ một đỉnh ngẫu nhiên, nhưng đối với đỉnh trình diễn này, đỉnh A được chọn làm đỉnh bắt đầu.

Từ đỉnh A, MST phát triển dọc theo cạnh có trọng số thấp nhất. Vậy đỉnh A và D bây giờ thuộc nhóm đỉnh thuộc Cây bao trùm tối thiểu.

Mảng parents là trọng tâm trong cách thuật toán của Prim phát triển các cạnh trong MST.

Tại thời điểm này, mảng parents trông như thế này:

 parents = [-1,  0, -1,  0,  3,  3, -1, -1]
#vertices [ A,  B,  C,  D,  E,  F,  G,  H]

Đỉnh A, đỉnh bắt đầu, không có đỉnh cha và do đó có giá trị -1 . Cha của Vertex D là A, đó là lý do tại sao giá trị cha của D là 0 (đỉnh A nằm ở chỉ số 0). Cha mẹ của B cũng là A, và D là cha mẹ của E và F.

Mảng parents giúp chúng ta giữ nguyên cấu trúc cây MST (một đỉnh chỉ có thể có một cha mẹ).

Ngoài ra, để tránh chu kỳ và theo dõi các đỉnh hiện có trong MST, mảng in_mst được sử dụng.

Mảng in_mst hiện tại trông như thế này:

 in_mst = [ true, false, false,  true, false, false, false, false]
#vertices [    A,     B,     C,     D,     E,     F,     G,     H]

Bước tiếp theo trong thuật toán của Prim là đưa thêm một đỉnh nữa vào làm một phần của MST và đỉnh gần nhất với các nút MST A và D hiện tại sẽ được chọn.

Vì cả AB và DF đều có cùng trọng số cạnh thấp nhất 4 nên B hoặc F có thể được chọn làm đỉnh MST tiếp theo. Chúng tôi chọn B làm đỉnh MST tiếp theo cho phần trình diễn này.

Như bạn thấy, cạnh MST tới E trước đây xuất phát từ đỉnh D, bây giờ nó xuất phát từ đỉnh B, vì BE có trọng số 6 thấp hơn DE có trọng số 7 . Vertex E chỉ có thể có một cha trong cấu trúc cây MST (và trong mảng parents ), do đó BE và DE không thể cùng là các cạnh MST của E.

Đỉnh tiếp theo trong MST là đỉnh C, vì cạnh BC có trọng số 3 là cạnh có trọng số ngắn nhất tính từ đỉnh MST hiện tại.

Vì đỉnh C được bao gồm trong MST, các cạnh ra khỏi C được kiểm tra để xem liệu có cạnh nào có trọng số thấp hơn từ đỉnh MST này đến các đỉnh bên ngoài MST hay không. Cạnh CE có trọng số ( 3 ) thấp hơn cạnh BE MST trước đó ( 6 ) và cạnh CH được đưa vào MST với trọng số cạnh 2 .

Đỉnh H là đỉnh tiếp theo được đưa vào MST, vì nó có trọng số cạnh thấp nhất 6 và đỉnh H trở thành đỉnh cha của đỉnh G trong mảng parents .

Đỉnh tiếp theo được đưa vào MST là E hoặc F vì chúng có trọng số cạnh thấp nhất: 4 .

Chúng tôi chọn đỉnh E làm đỉnh tiếp theo được đưa vào MST cho phần trình diễn này.

Hai đỉnh tiếp theo và cuối cùng được thêm vào MST là các đỉnh F và G. DF là cạnh MST đến F và EG là cạnh MST đến G vì các cạnh này là các cạnh có trọng số thấp nhất so với MST hiện tại.

Chạy mô phỏng bên dưới để xem thuật toán của Prim thực hiện các bước thủ công mà chúng ta vừa thực hiện.

Triển khai thuật toán Prim

Để thuật toán của Prim tìm Cây bao trùm tối thiểu (MST), chúng tôi tạo một lớp Graph . Sau này chúng ta sẽ sử dụng các phương thức bên trong lớp Graph này để tạo biểu đồ từ ví dụ trên và chạy thuật toán của Prim trên đó.

 class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

    def add_edge(self, u, v, weight):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.adj_matrix[u][v] = weight
            self.adj_matrix[v][u] = weight  # For undirected graph

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

Dòng 3-5: Lúc đầu, ma trận kề trống, nghĩa là không có cạnh nào trong đồ thị. Ngoài ra, các đỉnh không có tên để bắt đầu.

Dòng 7-10: Phương thức add_edge dùng để thêm một cạnh, với giá trị trọng số của cạnh, vào đồ thị vô hướng.

Dòng 12-14: Phương thức add_vertex_data được sử dụng để đặt tên cho các đỉnh, ví dụ như 'A' hoặc 'B'.

Bây giờ cấu trúc để tạo biểu đồ đã sẵn sàng, chúng ta có thể triển khai thuật toán Prim như một phương thức bên trong lớp Graph :

    def prims_algorithm(self):
        in_mst = [False] * self.size
        key_values = [float('inf')] * self.size
        parents = [-1] * self.size

        key_values[0] = 0  # Starting vertex

        print("Edge \tWeight")
        for _ in range(self.size):
            u = min((v for v in range(self.size) if not in_mst[v]), key=lambda v: key_values[v])

            in_mst[u] = True

            if parents[u] != -1:  # Skip printing for the first vertex since it has no parent
                print(f"{self.vertex_data[parents[u]]}-{self.vertex_data[u]} \t{self.adj_matrix[u][parents[u]]}")

            for v in range(self.size):
                if 0 < self.adj_matrix[u][v] < key_values[v] and not in_mst[v]:
                    key_values[v] = self.adj_matrix[u][v]
                    parents[v] = u

Dòng 17: Mảng in_mst chứa trạng thái của các đỉnh hiện có trong MST. Ban đầu, không có đỉnh nào là một phần của MST.

Dòng 18: Mảng key_values ​​giữ khoảng cách ngắn nhất hiện tại từ các đỉnh MST đến mỗi đỉnh bên ngoài MST.

Dòng 19: Các cạnh MST được lưu trữ trong mảng parents . Mỗi cạnh MST được lưu trữ bằng cách lưu trữ chỉ mục gốc cho mỗi đỉnh.

Dòng 21: Để đơn giản và làm cho mã này chạy giống như trong hoạt hình/ví dụ "Chạy qua thủ công" ở trên, đỉnh đầu tiên (đỉnh A ở chỉ số 0 ) được đặt làm đỉnh nhìn chằm chằm. Việc thay đổi chỉ mục thành 4 sẽ chạy thuật toán Prim từ đỉnh E và thuật toán đó cũng hoạt động tốt.

Dòng 25: Chỉ mục được tìm thấy cho đỉnh có giá trị khóa thấp nhất chưa thuộc MST. Hãy xem những giải thích này cho min và lambda để hiểu rõ hơn về dòng mã Python này.

Dòng 32-35: Sau khi một đỉnh mới được thêm vào MST (dòng 27), phần mã này sẽ kiểm tra xem liệu bây giờ có các cạnh từ đỉnh MST mới được thêm này có thể hạ giá trị khóa xuống các đỉnh khác bên ngoài MST hay không . Nếu đúng như vậy, mảng key_values ​​và mảng parents sẽ được cập nhật tương ứng. Có thể thấy rõ điều này trong hoạt ảnh khi một đỉnh mới được thêm vào MST và trở thành đỉnh hoạt động (hiện tại).

Bây giờ, hãy tạo biểu đồ từ "Chạy qua thủ công" ở trên và chạy thuật toán của Prim trên đó:

 class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

    def add_edge(self, u, v, weight):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.adj_matrix[u][v] = weight
            self.adj_matrix[v][u] = weight  # For undirected graph

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

    def prims_algorithm(self):
        in_mst = [False] * self.size
        key_values = [float('inf')] * self.size
        parents = [-1] * self.size

        key_values[0] = 0  # Starting vertex

        print("Edge \tWeight")
        for _ in range(self.size):
            u = min((v for v in range(self.size) if not in_mst[v]), key=lambda v: key_values[v])

            in_mst[u] = True

            if parents[u] != -1:  # Skip printing for the first vertex since it has no parent
                print(f"{self.vertex_data[parents[u]]}-{self.vertex_data[u]} \t{self.adj_matrix[u][parents[u]]}")

            for v in range(self.size):
                if 0 < self.adj_matrix[u][v] < key_values[v] and not in_mst[v]:
                    key_values[v] = self.adj_matrix[u][v]
                    parents[v] = u

g = Graph(8)

g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_vertex_data(7, 'H')

g.add_edge(0, 1, 4)  # A - B
g.add_edge(0, 3, 3)  # A - D
g.add_edge(1, 2, 3)  # B - C
g.add_edge(1, 3, 5)  # B - D
g.add_edge(1, 4, 6)  # B - E
g.add_edge(2, 4, 4)  # C - E
g.add_edge(2, 7, 2)  # C - H
g.add_edge(3, 4, 7)  # D - E
g.add_edge(3, 5, 4)  # D - F
g.add_edge(4, 5, 5)  # E - F
g.add_edge(4, 6, 3)  # E - G
g.add_edge(5, 6, 7)  # F - G
g.add_edge(6, 7, 5)  # G - H

print("Prim's Algorithm MST:")
g.prims_algorithm()

Độ phức tạp thời gian của thuật toán Prim

Để có giải thích chung về độ phức tạp của thời gian, hãy truy cập trang này .

Với \(V\) là số đỉnh trong đồ thị của chúng ta, độ phức tạp về thời gian của thuật toán Prim là

\[ O( V^2 ) \]

Lý do tại sao chúng ta gặp sự phức tạp về thời gian này là do các vòng lặp lồng nhau bên trong thuật toán của Prim (một vòng lặp for với hai vòng lặp for khác bên trong nó).

Vòng lặp for đầu tiên (dòng 24) đi qua tất cả các đỉnh trong biểu đồ. Điều này có độ phức tạp về thời gian \(O(V)\).

Vòng lặp for thứ hai (dòng 25) đi qua tất cả các đỉnh liền kề trong biểu đồ để tìm đỉnh có giá trị khóa thấp nhất nằm ngoài MST, sao cho nó có thể là đỉnh tiếp theo được đưa vào MST. Điều này có độ phức tạp về thời gian \(O(V)\).

Sau khi một đỉnh mới được đưa vào MST, vòng lặp for thứ ba (dòng 32) sẽ kiểm tra tất cả các đỉnh khác để xem liệu có cạnh đi ra từ đỉnh MST mới được thêm vào đến các đỉnh bên ngoài MST có thể dẫn đến giá trị khóa thấp hơn và được cập nhật hay không quan hệ cha mẹ. Điều này cũng có độ phức tạp về thời gian \(O(V)\).

Kết hợp độ phức tạp của thời gian lại với nhau, chúng ta có:

\[ \begin{equation} \begin{aligned} O(V)\cdot (O(V)+O(V)) & = O(V)\cdot (2\cdot O(V)) \\ & = O(V\cdot 2\cdot V) \\ & = O(2\cdot V^2) \\\\ & = O(V^2) \end{aligned} \end{equation} \]

Bằng cách sử dụng cấu trúc dữ liệu hàng đợi ưu tiên để quản lý các giá trị khóa, thay vì sử dụng mảng như chúng tôi làm ở đây, độ phức tạp về thời gian của thuật toán Prim có thể giảm xuống:

\[ O( E \cdot \log{V}) \]

Trong đó \(E\) là số cạnh trong đồ thị và \(V\) là số đỉnh.

Việc triển khai thuật toán Prim như vậy bằng cách sử dụng hàng đợi ưu tiên là tốt nhất cho các đồ thị thưa thớt. Đồ thị thưa thớt khi mỗi đỉnh chỉ được kết nối với một vài đỉnh khác.