Thuật toán Kruskal c++ | Code và bài tập

Cũng giống như thuật toán Prim, thuật toán Kruskal cũng tìm cây khung nhỏ nhất nhưng không phụ thuộc vào điểm bắt đầu. Bài viết dưới đây, TTnguyen sẽ trình bày lý thuyết, mô phỏng và cách cài đặt thuật toán kruskal c++.

Xem thêm:

• thuật toán prim
• thuật toán dijkstra

I. Tìm cây khung nhỏ nhất bằng thuật toán Kruskal

Các bước của thuật toán tìm cây phủ nhỏ nhất T của đồ thị liên thông có trọng số
như sau:

Bước 1: Đặt T = Ø (T rỗng không có cạnh)

Sắp xếp các cạnh của đồ thị theo thứ tự trọng số tăng dần vào tập Z

Bước 2: Trong khi (|T| < n-1) và Z≠Ø thức hiện:

• TÌm cạnh e có trọng số nhỏ nhất trong tập Z: Z= Z\{e}
• Nếu T ∪ {e} không tạo chu trình thì T = T ∪ {e}

II. Độ phức tạp của thuật toán Kruskal

Độ phức tạp của thuật toán Kruskal là O(E*log V), trong đó E là số cạnh và V là số đỉnh trong đồ thị.

III. Bài tập thuật toán Kruskal

Áp dụng thuật toán Kruskal xác định cây khung nhỏ nhất của đồ thị với trọng số như hình vẽ:

T = Ø, n=11

Lời giải

Tập cạnh của cây khung nhỏ nhất cần tìm là T = {(C,D), (C,F), (D,G), (A,E),
(B,E), (B,C), (G,M), (L,M), (A,K), (G,H)}, có tổng trọng số là: 41. Cây khung này
như hình dưới :

Bài 2: Hãy sử dụng thuật toán Kruskal tìm cây bao trùm nhỏ nhất của đồ thị G có chứa cạnh bc nhưng không chứa cạnh dh

Cây bao trùm nhỏ nhất không chứa cạnh dh của đồ thị G, ta loại cạnh dh ra
khỏi đồ thị, lúc này ta có đồ thị G’ với tập cạnh E’=E\{dh} như sau:

Khởi tạo T:= {(b,c)}.
Sắp xếp các cạnh của đồ thị theo thứ tự trọng số tăng dần trừ cạnh bc, ta có:
Z={(e,f), (k,l), (a,k), (d,g), (a,e), (b,f), (f,g), (h,m), (g,l), (a,b), (c,f), (c,d), (e,k),
(b,c), (l,m), (f,l), (g,m), (h,g) }.

Tập cạnh của cây khung nhỏ nhất cần tìm là T={(B,C), (E,F), (K,L), (A,K), (D,G),
(A,E), (B,F), (F,G), (H,M), (L,M)}, trọng số nhỏ nhất bằng : 35. Cây khung được
vẽ như sau:

IV. Giải thuật tìm cây khung nhỏ nhất

1. Phát biểu bài toán

Thuật toán sẽ xây dựng tập cạnh T của cây khung nhỏ nhất H=<V, T> theo từng bước như sau:
a. Sắp xếp các cạnh của đồ thị G theo thứ tự tăng dần của trọng số cạnh;
b. Xuất phát từ tập cạnh T=φ, ở mỗi bước, ta sẽ lần lượt duyệt trong danh sách các cạnh đã được sắp xếp, từ cạnh có trọng số nhỏ đến cạnh có trọng số lớn để tìm ra cạnh mà khi bổ sung nó vào T không tạo thành chu trình trong tập các cạnh đã được bổ sung vào T trước đó;
c. Thuật toán sẽ kết thúc khi ta thu được tập T gồm n-1 cạnh.

2. Mô tả thuật toán

void Kruskal() {
    T = ∅; // Khởi tạo cây khung bé nhất T rỗng.
    Trong khi (|T| < (n-1) và (E ≠ ∅)) {
        Chọn cạnh e ∈ E có độ dài nhỏ nhất; // Chọn cạnh e từ E có độ dài nhỏ nhất.
        E := E \ {e}; // Loại bỏ cạnh e khỏi tập cạnh còn lại.
        Nếu (T ∪ {e} không tạo thành chu trình) // Nếu thêm cạnh e vào T không tạo thành chu trình.
            T = T ∪ {e}; // Thêm cạnh e vào cây khung bé nhất T.
    }
    Nếu (|T| < n - 1)
        Đồ thị không liên thông; // Đồ thị không liên thông.
}

3. Code thuật toán Kruskal c

#include <stdio.h> 
#include <conio.h> 
#include <stdlib.h> 
#include <math.h> 
#include <dos.h> 
#define MAX 50 
#define TRUE 1 
#define FALSE 0 
int n, m, minl, connect; 
int dau[500],cuoi[500], w[500]; 
int daut[50], cuoit[50], father[50]; 
void Init(void){ 
 int i; FILE *fp; 
 fp=fopen("baotrum1.in","r"); 
 fscanf(fp, "%d%d", &n,&m); 
 printf("\n So dinh do thi:%d", n); 
 printf("\n So canh do thi:%d", m); 
 printf("\n Danh sach ke do thi:"); 
 for(i=1; i<=m;i++){ 
 fscanf(fp, "%d%d%d", &dau[i], &cuoi[i], &w[i]); 
 printf("\n Canh %d: %5d%5d%5d", i, dau[i], cuoi[i], w[i]); 
 } 
 fclose(fp);getch(); 
} 
void Heap(int First, int Last){ 
 int j, k, t1, t2, t3; 
 j=First; 
 while(j<=(Last/2)){ 
 if( (2*j)<Last && w[2*j + 1]<w[2*j]) 
 k = 2*j +1; 
 else 
 k=2*j;if(w[k]<w[j]){ 
 t1=dau[j]; t2=cuoi[j]; t3=w[j]; 
 dau[j]=dau[k]; cuoi[j]=cuoi[k]; w[j]=w[k]; 
 dau[k]=t1; cuoi[k]=t2; w[k]=t3; 
 j=k; 
 } 
 else j=Last; 
 } 
} 
int Find(int i){ 
 int tro=i; 
 while(father[tro]>0) 
 tro=father[tro]; 
 return(tro); 
} 
void Union(int i, int j){ 
 int x = father[i]+father[j]; 
 if(father[i]>father[j]) { 
 father[i]=j; 
 father[j]=x; 
 } 
 else { 
 father[j]=i; 
 father[i]=x; 
 } 
} 
void Krusal(void){ 
 int i, last, u, v, r1, r2, ncanh, ndinh; 
 for(i=1; i<=n; i++) 
 father[i]=-1; 
 for(i= m/2;i>0; i++) 
 Heap(i,m); last=m; ncanh=0; ndinh=0;minl=0;connect=TRUE; 
 while(ndinh<n-1 && ncanh<m){ 
 ncanh=ncanh+1; 
 u=dau[1]; v=cuoi[1]; 
 r1= Find(u); r2= Find(v); 
 if(r1!=r2) { 
 ndinh=ndinh+1; Union(r1,r2); 
 daut[ndinh]=u; cuoit[ndinh]=v; 
 minl=minl+w[1]; 
 } 
 dau[1]=dau[last]; 
 cuoi[1]=cuoi[last]; 
 w[1]=w[last]; 
 last=last-1; 
 Heap(1, last); 
 } 
 if(ndinh!=n-1) connect=FALSE; 
} 
void Result(void){ 
 int i; 
 printf("\n Do dai cay khung nho nhat:%d", minl); 
 printf("\n Cac canh cua cay khung nho nhat:"); 
 for(i=1; i<n; i++) 
 printf("\n %5d%5d",daut[i], cuoit[i]); 
 printf("\n"); 
} 
void main(void){ 
 clrscr(); Init(); 
 Krusal();Result(); getch(); 
}

Trên đây là bài tập và code thuật toán kruskal. Cảm ơn các bạn đã theo dõi toán rời rạc trên ttnguyen.net.