×

Cài đặt thuật toán Kruskal trong lập trình

Avatar of admin
admin 0 Views

Trong lĩnh vực khoa học máy tính, đặc biệt là trong nghiên cứu về lý thuyết đồ thị, thuật toán Kruskal được biết đến như một phương pháp hiệu quả để tìm kiếm cây khung nhỏ nhất (Minimum Spanning Tree - MST) của một đồ thị có trọng số. Bài viết này sẽ đi sâu vào việc cài đặt thuật toán này bằng lập trình, bao gồm các bước cơ bản và mã nguồn minh họa.

Tổng quan về thuật toán

Thuật toán Kruskal hoạt động dựa trên ý tưởng sắp xếp các cạnh của đồ thị theo thứ tự tăng dần của trọng số và liên tục thêm các cạnh nhỏ nhất vào cây khung nhỏ nhất, miễn là không tạo ra chu trình. Cụ thể, các bước của thuật toán có thể được tóm gọn như sau:

  1. Sắp xếp các cạnh: Sắp xếp tất cả các cạnh của đồ thị theo thứ tự tăng dần của trọng số.
  2. Khởi tạo rừng: Khởi tạo một rừng (forest) với mỗi đỉnh của đồ thị là một cây riêng biệt.
  3. Chọn cạnh: Liên tục chọn các cạnh nhỏ nhất, miễn là việc thêm cạnh đó vào không tạo ra chu trình (cycle) cho đến khi cây khung được hình thành đủ số lượng đỉnh - 1.

Cài đặt thuật toán

Để cài đặt thuật toán Kruskal, chúng ta cần một số cấu trúc dữ liệu cơ bản như danh sách cạnh (edge list) và một cấu trúc dữ liệu để quản lý tập hợp rời rạc (disjoint set). Giả sử chúng ta sử dụng ngôn ngữ lập trình Python cho minh họa này.

Khởi tạo dữ liệu

Trước hết, chúng ta cần định nghĩa các cấu trúc cần thiết:

class Edge:
    def __init__(self, u, v, weight):
        self.u = u
        self.v = v
        self.weight = weight

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

def union(parent, rank, x, y):
    root_x = find(parent, x)
    root_y = find(parent, y)

    if rank[root_x] < rank[root_y]:
        parent[root_x] = root_y
    elif rank[root_x] > rank[root_y]:
        parent[root_y] = root_x
    else:
        parent[root_y] = root_x
        rank[root_x] += 1

Triển khai thuật toán

Bây giờ, chúng ta sẽ triển khai thuật toán Kruskal:

def kruskal(edges, num_vertices):
    # Bước 1: Sắp xếp các cạnh theo trọng số tăng dần
    edges.sort(key=lambda edge: edge.weight)

    # Khởi tạo dữ liệu cho DSU (Disjoint Set Union)
    parent = []
    rank = []
    for node in range(num_vertices):
        parent.append(node)
        rank.append(0)

    mst_edges = []  # Danh sách các cạnh trong cây khung nhỏ nhất

    # Bước 2: Chọn các cạnh nhỏ nhất và kiểm tra chu trình
    for edge in edges:
        u = edge.u
        v = edge.v
        weight = edge.weight

        root_u = find(parent, u)
        root_v = find(parent, v)

        if root_u != root_v:
            mst_edges.append(edge)
            union(parent, rank, root_u, root_v)

    return mst_edges

Chạy thuật toán

Cuối cùng, chúng ta cần tạo ra một đồ thị và chạy thuật toán Kruskal trên đó:

if __name__ == "__main__":
    # Ví dụ đồ thị với 4 đỉnh và các cạnh có trọng số
    edges = [
        Edge(0, 1, 10),
        Edge(0, 2, 6),
        Edge(0, 3, 5),
        Edge(1, 3, 15),
        Edge(2, 3, 4)
    ]

    num_vertices = 4
    mst = kruskal(edges, num_vertices)

    print("Cây khung nhỏ nhất có các cạnh:")
    for edge in mst:
        print(f"{edge.u} -- {edge.v} == {edge.weight}")

Kết luận

Thuật toán Kruskal là một giải pháp tối ưu để tìm kiếm cây khung nhỏ nhất trong các đồ thị có trọng số nhờ vào sự sắp xếp và chọn lọc cạnh hiệu quả. Bài viết này đã cung cấp một cài đặt thuật toán Kruskal bằng lập trình Python, bao gồm các bước cơ bản và chi tiết mã nguồn. Hy vọng các lập trình viên sẽ tìm thấy bài viết này hữu ích trong việc nghiên cứu và ứng dụng thuật toán Kruskal.

Comments

Bài viết liên quan