Thuật toán DSA Kruskal

Thuật toán Kruskal

Thuật toán của Kruskal tìm Cây kéo dài tối thiểu (MST) hoặc Rừng kéo dài tối thiểu trong một biểu đồ vô hướng.

MST (hoặc MST) được thuật toán Kruskal tìm thấy là tập hợp các cạnh kết nối tất cả các đỉnh (hoặc càng nhiều càng tốt) với tổng trọng số cạnh tối thiểu.

Thuật toán của Kruskal thêm các cạnh vào MST (hoặc Rừng kéo dài tối thiểu), bắt đầu từ các cạnh có trọng số cạnh thấp nhất.

Các cạnh tạo chu trình sẽ không được thêm vào MST. Đây là những dòng nhấp nháy màu đỏ trong hình ảnh động ở trên.

Thuật toán của Kruskal kiểm tra tất cả các cạnh trong biểu đồ, nhưng hoạt ảnh ở trên sẽ dừng khi rừng MST hoặc Khoảng cách tối thiểu hoàn thành, do đó bạn không phải đợi kiểm tra các cạnh dài nhất.

Để tìm hiểu xem một cạnh có tạo chu trình hay không, chúng tôi sẽ sử dụng tính năng phát hiện chu trình Union-Find bên trong thuật toán Kruskal.

Chạy qua thủ công

Chúng ta hãy chạy qua thuật toán của Kruskal 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ó.

Ba cạnh đầu tiên được thêm vào MST. Ba cạnh này có trọng số cạnh thấp nhất và không tạo ra bất kỳ chu trình nào:

• CE, trọng lượng 2
• DE, trọng lượng 3
• AB, trọng lượng 4

Sau đó, cạnh CD (được biểu thị bằng màu đỏ) không thể được thêm vào vì nó sẽ dẫn đến một chu kỳ.

Bốn cạnh tiếp theo mà thuật toán Kruskal cố gắng thêm vào MST là:

• VD, cân nặng 6
• CG, trọng lượng 7 (không thêm)
• DF, trọng lượng 7
• BC, cân nặng 8

Không thể thêm Edge CG (được biểu thị bằng màu đỏ) vào MST vì nó sẽ tạo ra một chu trình.

Như bạn có thể thấy, MST đã được tạo vào thời điểm này, nhưng thuật toán Kruskal sẽ tiếp tục chạy cho đến khi tất cả các cạnh được kiểm tra để xem liệu chúng có thể được thêm vào MST hay không.

Ba cạnh cuối cùng mà thuật toán của Kruskal cố gắng thêm vào MST là những cạnh có trọng số cạnh cao nhất:

• AC, trọng lượng 9 (không thêm)
• AG, trọng lượng 10 (không thêm)
• FG, trọng lượng 11 (không thêm)

Mỗi cạnh này sẽ tạo ra một chu trình trong MST, vì vậy chúng không thể được thêm vào.

Thuật toán Kruskal đã hoàn thành.

Chạy mô phỏng bên dưới để xem thuật toán Kruskal 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 Kruskal

Để thuật toán của Kruskal tìm Cây kéo dài tối thiểu (MST) hoặc Rừng kéo dài tối thiểu, 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 Kruskal trên đó.

 class Graph:
    def __init__(self, size):
        self.size = size
        self.edges = []  # For storing edges as (weight, u, v)
        self.vertex_data = [''] * size  # Store vertex names

    def add_edge(self, u, v, weight):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.edges.append((weight, u, v))  # Add edge with weight
            
    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

Dòng 8 và 12: Kiểm tra xem các đối số đầu vào u , v và vertex , có nằm trong phạm vi có thể có của các giá trị chỉ mục hay không.

Để thực hiện phát hiện chu trình Union-Find trong thuật toán Kruskal, hai phương thức find và union này cũng được xác định bên trong lớp Graph :

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

Dòng 15-18: Phương thức find sử dụng mảng parent để tìm đệ quy gốc của một đỉnh. Đối với mỗi đỉnh, mảng parent chứa một con trỏ (chỉ mục) tới đỉnh cha của đỉnh đó. Đỉnh gốc được tìm thấy khi phương thức find đến một đỉnh trong mảng parent trỏ đến chính nó. Hãy tiếp tục đọc để biết cách sử dụng phương thức find và mảng parent bên trong phương thức kruskals_algorithm .

Dòng 20-29: Khi một cạnh được thêm vào MST, phương thức union sử dụng mảng parent để hợp nhất (kết hợp) hai cây. Mảng xếp rank chứa ước tính sơ bộ về chiều cao của cây cho mỗi đỉnh gốc. Khi hợp nhất hai cây, gốc có thứ hạng thấp hơn sẽ trở thành con của đỉnh gốc của cây kia.

Đây là cách thuật toán Kruskal được triển khai như một phương thức bên trong lớp Graph :

    def kruskals_algorithm(self):
        result = []  # MST
        i = 0 # edge counter

        self.edges = sorted(self.edges, key=lambda item: item[2])

        parent, rank = [], []

        for node in range(self.size):
            parent.append(node)
            rank.append(0)

        while i < len(self.edges):
            u, v, weight = self.edges[i]
            i += 1

            x = self.find(parent, u)
            y = self.find(parent, v)
            if x != y:
                result.append((u, v, weight))
                self.union(parent, rank, x, y)

        print("Edge \tWeight")
        for u, v, weight in result:
            print(f"{self.vertex_data[u]}-{self.vertex_data[v]} \t{weight}")

Dòng 35: Các cạnh phải được sắp xếp trước khi thuật toán Kruskal bắt đầu cố gắng thêm các cạnh vào MST.

Dòng 40-41: Mảng parent và mảng rank được khởi tạo. Để bắt đầu, mỗi đỉnh là gốc riêng của nó (mọi phần tử trong mảng parent đều trỏ đến chính nó) và mọi đỉnh đều không có chiều cao (giá trị 0 trong mảng rank ).

Dòng 44-45: Chọn cạnh nhỏ nhất và tăng i sao cho cạnh đúng được chọn trong lần lặp tiếp theo.

Dòng 47-51: Nếu các đỉnh u và v ở mỗi đầu của cạnh hiện tại có gốc x và y khác nhau, điều đó có nghĩa là sẽ không có chu trình cho cạnh mới và các cây được hợp nhất. Để hợp nhất các cây, cạnh hiện tại được thêm vào mảng result và chúng tôi chạy phương thức union để đảm bảo các cây được hợp nhất chính xác, sao cho chỉ có một đỉnh gốc trong cây được hợp nhất thu được.

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 Kruskal trên đó:

 class Graph:
    def __init__(self, size):
        self.size = size
        self.edges = []  # For storing edges as (weight, u, v)
        self.vertex_data = [''] * size  # Store vertex names

    def add_edge(self, u, v, weight):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.edges.append((u, v, weight))  # Add edge with weight
            
    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

    def kruskals_algorithm(self):
        result = []  # MST
        i = 0  # edge counter

        self.edges = sorted(self.edges, key=lambda item: item[2])

        parent, rank = [], []

        for node in range(self.size):
            parent.append(node)
            rank.append(0)

        while i < len(self.edges):
            u, v, weight = self.edges[i]
            i += 1
            
            x = self.find(parent, u)
            y = self.find(parent, v)
            if x != y:
                result.append((u, v, weight))
                self.union(parent, rank, x, y)

        print("Edge \tWeight")
        for u, v, weight in result:
            print(f"{self.vertex_data[u]}-{self.vertex_data[v]} \t{weight}")

g = Graph(7)
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_edge(0, 1, 4)  #A-B,  4
g.add_edge(0, 6, 10) #A-G, 10
g.add_edge(0, 2, 9)  #A-C,  9
g.add_edge(1, 2, 8)  #B-C,  8
g.add_edge(2, 3, 5)  #C-D,  5
g.add_edge(2, 4, 2)  #C-E,  2
g.add_edge(2, 6, 7)  #C-G,  7
g.add_edge(3, 4, 3)  #D-E,  3
g.add_edge(3, 5, 7)  #D-F,  7
g.add_edge(4, 6, 6)  #E-G,  6
g.add_edge(5, 6, 11) #F-G, 11

print("Kruskal's Algorithm MST:")
g.kruskals_algorithm()

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

Để 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 \(E\) là số cạnh trong biểu đồ của chúng ta, độ phức tạp về thời gian của thuật toán Kruskal là

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

Lần này chúng ta gặp sự phức tạp vì các cạnh phải được sắp xếp trước khi Kruskal có thể bắt đầu thêm các cạnh vào MST. Việc sử dụng thuật toán nhanh như Sắp xếp nhanh hoặc Sắp xếp hợp nhất sẽ mang lại cho chúng ta độ phức tạp về thời gian \( O( E \cdot log{E} ) \) chỉ riêng cho việc sắp xếp này.

Sau khi các cạnh được sắp xếp, tất cả chúng đều được kiểm tra từng cái một để xem liệu chúng có tạo chu trình hay không và nếu không, chúng sẽ được thêm vào MST.

Mặc dù có vẻ như có rất nhiều công việc phải làm để kiểm tra xem một chu trình có được tạo bằng phương pháp find hay không và sau đó đưa một cạnh vào MST bằng phương pháp union , nhưng điều này vẫn có thể được xem là một thao tác. Lý do chúng ta có thể coi đây chỉ là một thao tác là vì nó mất thời gian gần như không đổi. Điều đó có nghĩa là thời gian của thao tác này tăng lên rất ít khi biểu đồ phát triển và do đó nó thực sự không góp phần vào độ phức tạp về thời gian tổng thể.

Do độ phức tạp về thời gian của thuật toán Kruskal chỉ thay đổi theo số cạnh \(E\), nên nó đặc biệt nhanh đối với các đồ thị thưa thớt trong đó tỷ lệ giữa số cạnh \(E\) và số đỉnh \(V\) là tương đối thấp.