[Thuật toán] Tìm cây khung nhỏ nhất

Bài toán cây khung nhỏ nhất của đồ thị là một trong số những bài toán tối ưu trên đồ thị được ứng dụng trong nhiều lĩnh vực khác nhau của đời sống. Trong mục này chúng ta sẽ trình bày những thuật toán cơ bản để giải bài toán này. Trước hết chúng ta phát biểu nội dung của bài toán.
     Cho G = (V, E) là đồ thị vô hướng liên thông với tập đỉnh V = {1,2,..., n} và tập cạnh E gồm m cạnh. Mỗi cạnh e của đồ thị G được gán với một số thực c(e), gọi là độ dài của nó. Giả xử H = (V, T) là cây khung của đồ thị. Ta gọi độ dài c(H) của cây khung H là tổng độ dài của các cạnh của nó:

c(H) = SUM(c(e)) ; e thuộc T

Bài toán đặt ra là trong số tất cả các cây khung của đồ thị G hãy tìm cây khung với độ dài nhỏ nhất. Cây khung như vậy được gọi là cây khung nhỏ nhất của đồ thị và bài toán đặt ra được gọi là bài toán cây khung nhỏ nhất.
Bài toán xây dựng hệ thống đường sắt: Giả sử ta muốn xây dựng hệ thống đường sắt nối n thành phố sao cho hành khách có thể đi từ bất cứ thành phố nào đến bất kỳ một trong các thành phố còn lại. Mặt khác trên quan điểm kinh tế đòi hỏi là chi phí về  xây dựng hệ thống đường phải là nhỏ nhất. Rõ ràng là đồ thị mà đỉnh là các thành phố còn các cạnh là các tuyến đường sắt nối các thành phố tương ứng với phương án tối ưu phải là cây. Vì vậy, bài toán đặt ra dẫn về bài toán tìm cây khung nhỏ nhất trên đồ thị đầy đủ n đỉnh, mỗi đỉnh tương ứng với một thành phố, với độ dài trên các cạnh chính là chi phí xây dựng đường ray nối hai thành phố tương ứng.
Bài toán nối mạng máy tính: Cần nối mạng một hệ thống gồm n máy vi tính đánh số từ 1 đến n. Biết chi phí nối máy I với máy j là c[i,j] , i,j = 1,2…,n. Hãy tìm cách nối mạng là nhỏ nhất.
Trong đó thuật toán Kruskal và Thuật toán Prim là hai thuật toán phổ biến và nổi tiếng để tìm cây khung nhỏ nhất.

1. Thuật toán Kruskal
2. Thuật toán Prim

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.