Thuật toán Kruskal làm việc kém hiệu quả đối với những đồ thị có số cạnh khoảng m=n(n-1)/2. Trong những tình huống như vậy, thuật toán Prim giải tay tìm cây khung nhỏ nhất tỏ ra hiệu quả hơn. Bài viết dưới đây, TTnguyen sẽ cùng các bạn tìm hiểu lý thuyết, bài tập mô phỏng và cách cài đặt Prim.
Xem thêm:
I. Thuật toán Prim (Prim’s Algorithm)
Trong thuật toán này, bắt đầu tại một đỉnh tuỳ ý s của đồ thị, nối s với đỉnh y sao cho trọng số cạnh c[s, y] là nhỏ nhất. Tiếp theo, từ đỉnh s hoặc y tìm cạnh có độ dài nhỏ nhất, điều này dẫn đến đỉnh thứ ba z và ta thu được cây bộ phận gồm 3 đỉnh 2 cạnh. Quá trình được tiếp tục cho tới khi ta nhận được cây gồm n-1 cạnh, đó chính là cây bao trùm nhỏ nhất cần tìm.
Bài toán tìm cây khung nhỏ nhất của một đồ thị là một trong những bài toán tối ưu trên đồ thị có rất nhiều ứng dụng trong thực tế. Để minh họa cho thuật toán này, ta có thể xem xét một số mô hình thực tế điển hình:
- Bài toán xây dựng đường giao thông: Giả sử chúng ta cần xây dựng một hệ thống đường bộ để kết nối n thành phố, đảm bảo rằng giữa bất kỳ hai thành phố nào cũng có một con đường. Nhiệm vụ đặt ra là tìm cây khung nhỏ nhất trên đồ thị, trong đó mỗi thành phố là một đỉnh và mục tiêu là tối thiểu hóa tổng chi phí xây dựng hệ thống đường giao thông này.
- Bài toán nối mạng máy tính: Giả sử có n máy tính cần kết nối với nhau trong một hệ thống mạng. Biết rằng chi phí kết nối giữa máy i và máy j là c[i,j], với i,j = 1, 2, …, n (thông thường, chi phí này phụ thuộc vào độ dài cáp kết nối). Mục tiêu là tìm ra cách kết nối sao cho tổng chi phí nối mạng là thấp nhất.
Một số khái niệm:
- Cây khung là một tập các cạnh sao cho tập cạnh này không tồn tại chu trình và liên thông
- Cây khung nhỏ nhất là cây khung mà tổng trọng số các cạnh thuộc cây khung là nhỏ nhất
Tải full bài tập thực hành lập trình C/C++ có lời giải:
II. Độ phức tạp của thuật toán Prim
Độ phức tạp thời gian của thuật toán Prim là O(E log V), trong đó E là số cạnh và V là số đỉnh trong đồ thị. Độ phức tạp không gian của thuật toán Prim là O(V + E).
III. Bài tập giải tay thuật toán Prim
Bài 1: Dùng thuật toán Prim tìm cây khung nhỏ nhất của đồ thị có ma trận trọng số sau:
Giải
Tập cạnh của cây khung nhỏ nhất cần tìm là T={(X1,X3), (X3,X2), (X2,X8), (X8,X4), (X8,X6), (X6,X7), (X1,X5)} trọng số nhỏ nhất bằng : 13+15+12+19+14+17+11 = 101. Cây khung được vẽ như sau:
Bài 2: Tìm cây bao trùm ngắn nhất prim:
Giải
Bước 1: \( X_1 = { 1}, V_1 = {∅} \)
Bước 2: \( X_2 = { 1,2}, V_2 = {(1,2)} \)
Bước 3: \( X_3 = { 1,2,3}, V_3 = {(1,2),(2,3)} \)
Bước 4: \( X_4 = { 1,2,3,4}, V_4 = {(1,2),(2,3),(3,4)} \)
Bước 5: \( X_5 = { 1,2,3,4,6}, V_5 = {(1,2),(2,3),(3,4),(3,6)} \)
Bước 6: \( X_6 = X_5 ∪ {7}, V_6 = V_5 ∪ {(6,7)} \)
Bước 7: \( X_7 = X_6 ∪ {5}, V_7 = V_6 ∪ {(6,5)} \)
Bước 8: \( X_8 = X_7 ∪ {8}, V_8 = V_7 ∪ {(5,8)} \)
Bước 9: \( X_9 = X_8 ∪ {11}, V_9 = V_8 ∪ {(8,11)} \)
Bước 10: \( X_{10} = X_9 ∪ {9}, V_{10} = V_9 ∪ {(8,9)} \)
Bước 11: còn lại đỉnh 10, đỉnh gần đỉnh 10 nhất là đỉnh \(9 X_{11} = X_{10} ∪ {10}, V_{11} = V_{10} ∪ {(9,10)} \)
IV. Cài đặt thuật toán Prim c++
1. Mô tả thuật toán Prim
Các bước chính của thuật toán Prim tìm cây phủ nhỏ nhất T của đồ thị liên thông có trọng số G được mô tả như sau:
Bước 1 : T := {v} v là đỉnh bất kỳ.
Bước 2 : Lặp n-1 lần
– Tìm đỉnh rìa v có cạnh e nối T với trọng số nhỏ nhất
– Đưa e vào T
2. Code thuật toán Prim
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#include <dos.h>
#define TRUE 1
#define FALSE 0
#define MAX 10000
int a[100][100];
int n, m, i, sc, w;
int chuaxet[100];
int cbt[100][3];
FILE * f;
void nhap(void) {
int p, i, j, k;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
a[i][j] = 0;
f = fopen("baotrum.in", "r");
fscanf(f, "%d%d", & n, & m);
printf("\n So dinh: %3d ", n);
printf("\n So canh: %3d", m);
printf("\n Danh sach canh:");
for (p = 1; p <= m; p++) {
fscanf(f, "%d%d%d", & i, & j, & k);
printf("\n %3d%3d%3d", i, j, k);
a[i][j] = k;
a[j][i] = k;
}
for (i = 1; i <= n; i++) {
printf("\n");
for (j = 1; j <= n; j++) {
if (i != j && a[i][j] == 0)
a[i][j] = MAX;
printf("%7d", a[i][j]);
}
}
fclose(f);
getch();
}
void Result(void) {
for (i = 1; i <= sc; i++)
printf("\n %3d%3d", cbt[i][1], cbt[i][2]);
}
void PRIM(void) {
int i, j, k, top, min, l, t, u;
int s[100];
sc = 0;
w = 0;
u = 1;
for (i = 1; i <= n; i++)
chuaxet[i] = TRUE;
top = 1;
s[top] = u;
chuaxet[u] = FALSE;
while (sc < n - 1) {
min = MAX;
for (i = 1; i <= top; i++) {
t = s[i];
for (j = 1; j <= n; j++) {
if (chuaxet[j] && min > a[t][j]) {
min = a[t][j];
k = t;
l = j;
}
}
}
sc++;
w = w + min;
cbt[sc][1] = k;
cbt[sc][2] = l;
chuaxet[l] = FALSE;
a[k][l] = MAX;
a[l][k] = MAX;
top++;
s[top] = l;
printf("\n");
}
}
void main(void) {
clrscr();
nhap();
PRIM();
printf("\n Do dai ngan nhat:%d", w);
for (i = 1; i <= sc; i++)
printf("\n %3d%3d", cbt[i][1], cbt[i][2]);
getch();
}
Trên đây là lý thuyết và bài tập vận dụng thuật toán prim toán rời rạc. Cảm ơn các bạn đã tham khảo trên ttnguyen.net
Bài viết liên quan:
