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 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.
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 về 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:
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
