Bài viết Thuật toán Prim tìm cây khung nhỏ nhất
thuộc chủ đề về Hỏi & Đáp
thời gian này đang được rất nhiều bạn quan tâm đúng không nào !!
Hôm nay, Hãy cùng Hlink.Vn tìm hiểu
Thuật toán Prim tìm cây khung nhỏ nhất trong bài viết hôm nay nhé !
Các bạn đang xem bài viết : “Thuật toán Prim tìm cây
khung nhỏ nhất”
Đánh giá về Thuật toán Prim tìm cây khung nhỏ nhất
Xem nhanh
Mã giả thuật toán PRIM tại: https://dadv98.blogspot.com/2022/07/li-thuyet-o-thi.html
Đăng kí theo dõi kênh tại đây: https://bitly.com.vn/kd4Qz
Xem đầy đủ Playlist về Lí thuyết đồ thị tại: https://bitly.com.vn/iXzQ3
This entry is part 13 of 16 in the seriesCấu trúc dữ liệu
92 / 100
Thuật toán Prim (tiếng anh: Prim’s algorithm) là một thuật toán tham lam được sử 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 vài thuật ngữ liên quan:
- Spanning Tree : là cây khung của đồ thị liên thông và vô hướng, (Cho nên thuật toán này chỉ dùng cho đồ thị vô hướng).
- Minimum Spanning Tree : là cây khung nhỏ nhất, (Có tổng trọng số của các cạnh là nhỏ nhất).
NỘI DUNG BÀI VIẾT
Ý tưởng thuật toán Prim
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:
- Bước 1. Khởi tạo tập hợp đỉnh V rỗng, tập hợp cạnh E rỗng.
- Bước 2. Chọn ngẫu nhiên 1 đỉnh và thêm vào tập hợp các đỉnh V.
- Bước 3. Chọn 1 đỉnh chưa có trong tập V mà có liên kết với 1 đỉnh trong V, cạnh tạo từ 2 đỉnh đó phải là cạnh có trọng số nhỏ nhất và thêm vào tập hợp các cạnh E.
- Bước 4. Lặp lại bước 3 cho đến khi cây khung hoàn thành (Cách nhận biết cây khung hoàn thành là tất cả các đỉnh của cây khung đều đặn đã xuất hiện trong V), cây khung nhỏ nhất là cây khung được tạo từ tập các cạnh trong E.
✅ Mọi người cũng xem : tình thương tiếng anh là gì
Ví dụ của thuật toán Prim
Nế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.
- Có đồ thị G=(V, E) Có V đỉnh và E cạnh.
- Tập hợp các đỉnh của đồ thị V = 1, 2, 3, 4, 5, 6 (Viết tắt của vertex nghĩa là đỉnh).
- Tập hợp các cạnh của E = (1, 2), (1, 3), (1, 4), (2, 3), (2, 5), (3, 4), (3, 5), (3, 6), (4, 6), (5, 6) (Viết tắt của edge nghĩa là cạnh).
- Ta tạo ra 2 tập hợp U và T, U là tập hợp các đỉnh và T là tập hợp các cạnh tạo ra cây khung nhỏ nhất.
- Ban đầu U=Ø (rỗng) và T=Ø.
Bước 1. Khởi tạo
- Ta tạo ra 2 tập hợp U và T, U là tập hợp các đỉnh và T là tập hợp các cạnh tạo ra cây khung nhỏ nhất.
- Ban đầu U=Ø (rỗng) và T=Ø.
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 tổng 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 xuất hiện trong T mà 1 đỉnh của nó trong U. Ta tìm được cạnh (3,2) với tổng 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.
Cây khung nhỏ nhất mà chúng ta tìm được bằng thuật
toán Prim.
Hình ảnh động dưới đây mô phỏng lại quy 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).
- Tập hợp các cạnh T=(1, 3), (3, 6), (6, 4), (3, 2), (2, 5) tạo thành cây khung có tổng trọng số nhỏ nhất. Tổng trọng số của cây khung nhỏ nhất là:1 + 4 + 2 + 5 + 3 = 15
So sánh 2 cây khung (ban đầu, bên trái) và cây khung
nhỏ nhất tìm được bằng thuật toán Prim (bên phải).
Code giải thuật Prim
Dướ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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
intprims() intcost[MAX][MAX]; intu,v,min_distance,distance[MAX],from[MAX]; intvisited[MAX],no_of_edges,i,min_cost,j; //Tạo cost[][](giá trị) của ma trận for(i=0;i<n;i++) for(j=0;j<n;j++) if(G[i][j]==0) //Nếu trong cây khung không có cạnh nối giữa 2 điểm i, j(Là G[i][j]==0) cost[i][j]=infinity; //Thì gán tổng giá trị của cạnh i, j =infinity(Là 1 số cực lớn ở đây là 9999) else cost[i][j]=G[i][j]; //Nếu có cạnh nối giữa 2 điểm i, j thì gán giá trị của cạnh =G[i][j] spanning[i][j]=0; //Khởi tạo visited[],distance[] and from[] distance[0]=0; visited[0]=1; for(i=1;i<n;i++) distance[i]=cost[0][i]; from[i]=0; visited[i]=0; min_cost=0;//giá trị của cây khung no_of_edges=n-1;//Số cạnh được thêm vào. while(no_of_edges>0) //Tìm đỉnh có khoảng cách nhỏ nhất đến cây min_distance=infinity; //Gán min_distance=infinity for(i=1;i<n;i++) if(visited[i]==0&&distance[i]<min_distance) //Mục đích của việc gán min_distance=infinity là để xác nhận distance[i] khác 0
v=i; min_distance=distance[i]; u=from[v]; //Chèn cạnh vào cây khung spanning[u][v]=distance[v]; spanning[v][u]=distance[v]; no_of_edges–; visited[v]=1; //Cập nhật distance[](khoảng cách) vào mảng for(i=1;i<n;i++) if(visited[i]==0&&cost[i][v]<distance[i])
distance[i]=cost[i][v]; from[i]=v; min_cost=min_cost+cost[u][v]; return(min_cost); |
Full code thuật toán Prim
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
#include<stdio.h> #define infinity 9999 #define MAX 20 intG[MAX][MAX],spanning[MAX][MAX],n; intprims(); intReadMatrix(charfilepath[]); voidOutputMatrix(); intReadMatrix(charfilepath[]) FILE*f=fopen(filepath,”r”); if(f==NULL) printf(“nCant open file”); return0; fscanf(f,”%d”,&n); for(inti=0;i<n;i++) for(intj=0;j<n;j++) fscanf(f,”%d”,&G[i][j]); fclose(f); return1; voidOutputMatrix() printf(“Number of Vertices: %dn”,n); for(inti=0;i<n;i++) printf(“n”); for(intj=0;j<n;j++) printf(“%dt”,G[i][j]); intmain() inti,j,total_cost; ReadMatrix(“Prim.txt”); total_cost=prims(); printf(“nSpanning Tree Matrix:n”); OutputMatrix(); printf(“nnTotal cost of spanning tree=%d”,total_cost); return0; intprims() intcost[MAX][MAX]; intu,v,min_distance,distance[MAX],from[MAX]; intvisited[MAX],no_of_edges,i,min_cost,j; for(i=0;i<n;i++) for(j=0;j<n;j++) if(G[i][j]==0) cost[i][j]=infinity; else cost[i][j]=G[i][j]; spanning[i][j]=0; distance[0]=0; visited[0]=1; for(i=1;i<n;i++) distance[i]=cost[0][i]; from[i]=0; visited[i]=0; min_cost=0;//cost of spanning tree no_of_edges=n-1;//no. of edges to be added while(no_of_edges>0) min_distance=infinity; for(i=1;i<n;i++) if(visited[i]==0&&distance[i]<min_distance)
v=i; min_distance=distance[i]; u=from[v]; spanning[u][v]=distance[v]; spanning[v][u]=distance[v]; no_of_edges–; visited[v]=1; for(i=1;i<n;i++) if(visited[i]==0&&cost[i][v]<distance[i])
distance[i]=cost[i][v]; from[i]=v; min_cost=min_cost+cost[u][v]; return(min_cost); |
Dữ liệu vào:
60 6 1 5 0 06 0 5 0 3 01 5 0 5 6 45 0 5 0 0 20 3 6 0 0 60 0 4 2 6 0
Lưu ý:
- một số giáo trình hay một vài nơi sẽ ghi số 0 thành kí hiệu vô cùng.
- Khi tạo file .txt thì nên bỏ chung cùng thư mục với bài làm để tránh sai sót không đáng có.
Kết quả thực thi của code theo ví dụ đầu vào phía trên:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Spanning Tree Matrix: Number of Vertices:6 061500 605030 150564 505002 036006 004260 Total cost of spanning tree=15 |
✅ Mọi người cũng xem : học tập hiệu quả là gì
Độ phức tạp thuật toán
| Cấu trúc dữ liệu tìm cạnh có trọng số nhỏ nhất | Độ phức tạp |
| Tìm kiếm trên ma trận kề | O(V2) |
| Đống nhị phân và danh sách kề | O((V + E) log V) = O(E log V) |
| Đống Fibonacci và danh sách kề | O(E + V log V) |
Code cài đặt phía trên đang sử dụng tìm kiếm trên ma trận kề có độ phức tạp là O(V2). Bạn cũng có khả năng cài đặt lại thuật toán Prim sử dụng danh sách kề.
✅ Mọi người cũng xem : các bài tập kháng lực là gì
Ứng dụng của cây khung nhỏ nhất
Với bài toán tìm cây khung nhỏ nhất, chúng ta có khả năng áp dụng để giải quyết & tối ưu rất nhiều bài toán trong thực tế. Ví dụ với bài toán lắp đặt hệ thống mạng cho 1 trường học:
- Tất cả các phòng cần có liên kết internet.
- Biết trước khoảng cách giữa 2 phòng bất kỳ
- Bài toán: Làm sao lắp đặt hệ thống mạng cho trường học này với chi phí tối thiếu (giả sử chi phí tỉ lệ thuận với khoảng cách).
Trên đây là nội dung bài viết về thuật toán Prim đi kèm code sử dụng ngôn ngữ C. Trong quy trình viết khó tránh khỏi sai sót , nếu có thắc mắc hay góp ý thì hãy bình luận bên dưới hoặc qua nhóm Lập Trình Không Khó để giải đáp thêm các thắc mắc các bạn vướng phải trong quá trình tìm hiểu.
Các câu hỏi về thuật toán prim là gì
Nếu có bắt kỳ câu hỏi thắc mắt nào vê thuật toán prim là gì hãy cho chúng mình biết nhé, mõi thắt mắt hay góp ý của các bạn sẽ giúp mình cải thiện hơn trong các bài sau nhé
Trả lời