Bài toán cây khung nhỏ nhất min tree c++
|
Cây khung (Spanning Tree): là một cây con của đồ thị, tập hợp các cạnh của đồ thị thỏa mãn tập cạnh này không chứa chu trình và liên thông. Show
THUẬT TOÁN
Bước 1: Xóa các vòng và các cạnh song song Xóa các vòng cà các cạnh song song từ đồ thị đã cho. Khi xóa các cạnh song song, giữ lại cạnh có trọng số nhỏ nhất và xóa cạnh còn lại. Sau khi thêm nút D vào cây khung, chúng ta còn 2 cạnh có cùng trọng số 2 là DT và DB. Ta tiếp tục thêm 2 cạnh này vào cây khung Từ đó, ta đã có một cây khung nhỏ nhất hoàn chỉnh:
Bước 1: Xóa tất cả các vòng và các cạnh song song Xóa các vòng và các cạnh song song. Khi xóa các cạnh song song, giữ cạnh có trọng số nhỏ nhất và xóa cạnh còn lại. Bước 2: Sắp xếp tất cả các cạnh theo trọng số tăng dần Tạo một tập các cạnh và trọng số. Sắp xếp chúng theo thứ tự tăng dần về trọng số. Bước 3: Thêm một cạnh có trọng số nhỏ nhất Bắt đầu thêm các cạnh của đồ thị từ cạnh có trọng số thấp nhất. Kiểm tra các thuộc tính của cây khung, nếu phá vỡ thuộc tính thì bỏ cạnh đó. Thuật toán Prim (tiếng anh: Prim’s algorithm) là một thuật toán tham lam được dùng để tìm cây khung nhỏ nhất (Minimum Spanning Tree – MST) của một đồ thị liên thông có trọng số. Thuật toán được tìm ra vào năm 1975 và được đặt tên theo nhà nghiên cứu khoa học máy tính Robert C. Prim. Một số thuật ngữ liên quan:
Thuật toán Prim sẽ bắt đầu bằng việc chọn ngẫu nhiên một đỉnh bất kì và tiếp tục thêm các cạnh có trọng số nhỏ nhất cho đến khi có đủ tập hợp các đỉnh. Các bước để thực hiện:
Ví dụ của thuật toán PrimNếu bạn cảm thấy chưa hiểu rõ thì đừng lo chúng ta sẽ đi vào phần ví dụ và hình ảnh chắc chắn bạn sẽ cảm thấy dễ hiểu hơn đấy. Hãy quan sát ví dụ với cây khung đầy đủ dưới đây.
Bước 1. Khởi tạo
Bước 2. Chọn 1 đỉnh ngẫu nhiên từ cây khung trên, ví dụ chúng ta chọn đỉnh 1. Sau bước này, ta có U={1} và T={Ø}. Bước 3. Tìm tất cả các cạnh có 1 đỉnh ở trong U. Ở đây, ta sẽ tìm được cạnh (1, 3) do khoảng cách nhỏ nhất với giá trị là 1. Sau bước này ta có U={1, 3} và T={(1, 3)}. Bước 4. Tương tự bước 3, ta đi tìm cạnh nhỏ nhất có 1 đỉnh trong U mà cạnh đó chưa có trong V. Kết quả là ta tìm ra cạnh (3, 6) với giá trị 4. Sau bước này ta có U={1, 3, 6} và T={(1, 3), (3, 6)}. Bước 5. Do tập U mới chỉ có 3/6 đỉnh, ta tiếp tục đi tìm cạnh nhỏ nhất chưa khám phá mà 1 đỉnh của nó trong U. Kết quả là ta tìm được cạnh (6, 4). Bây giờ U={1, 3, 6, 4} và T={(1, 3), (3, 6), (6, 4)}. Bước 6. Do tập U mới chỉ có 4/6 đỉnh, tiếp tục tìm cạnh nhỏ nhất chưa có trong T mà 1 đỉnh của nó trong U. Ta tìm được cạnh (3,2) với giá trị 5. Sau buớc này U={1, 3, 6, 4, 2} và T={(1, 3), (3, 6), (6, 4), (3, 2)}. Bước 7. Do tập U mới chỉ có 5/6 đỉnh, tiếp tục tìm cạnh nhỏ nhất chưa có trong T mà 1 đỉnh của nó trong U. Ta tìm được cạnh (2, 5) với giá trị 3. Lúc này tập U đã có 6/6 đỉnh nên thuật toán kết thúc. Hình ảnh động dưới đây mô phỏng lại quá trình tìm kiếm cây khung nhỏ nhất cho ví dụ từng bước ở trên: Sau khi áp dụng xong thuật toán Prim, ta có U={1, 3, 6, 4, 2, 5} và T={(1, 3), (3, 6), (6, 4), (3, 2), (2, 5)}.
Code giải thuật PrimDưới đây là hàm chính thực thi giải thuật Prim biểu diễn đồ thi bằng ma trận kề, đi kèm với hướng dẫn bằng comment. int prims(){
int cost[MAX][MAX];
int u,v,min_distance,distance[MAX],from[MAX];
int visited[MAX],no_of_edges,i,min_cost,j;
//Tạo cost][ của ma trận
for(i=0;i include
define infinity 9999define MAX 20int G[MAX][MAX],spanning[MAX][MAX],n; int prims(); int ReadMatrix(char filepath[] ); void OutputMatrix(); int ReadMatrix(char filepath[] ) { FILE* f = fopen(filepath,"r"); if(f==NULL) { for(int j=0;j |
