Thuật toán về Kruskal - Tìm cây khung nhỏ nhất bằng C/C++

Thuật toán về Kruskal - Tìm cây khung nhỏ nhất bằng C/C++

Xem thuật toán Prim - tìm cây khung nhỏ nhất tại đây.

>> Lý thuyết và bài tập mẫu thuật toán (Prime) cây bao trùm cài đặt C/C++

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:

1.  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;

2.  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 đó;

3.  Thuật toán sẽ kết thúc khi ta thu được tập T gồm n-1 cạnh.

Thuật toán được mô tả thông qua thủ tục Kruskal như sau:

void  Kruskal(void){

 T = φ;

 While(| T | < (n - 1) and(E≠ φ)){

  Chọn cạnh e ∈E là cạnh có độ dài nhỏ nhất;

 E: = E\ {e};

  if (T ∪{ e }: không tạo nên chu trình)

   T = T ∪{ e };

 }

 if (| T | <n - 1)

  Đồ thị không liên thông;

}

Khối lượng tính toán nhiều nhất cảu thuật toán chính là ở bước sắp xếp các cạnh của đồ thị theo thứ tự không giảm của độ dài các cạnh để bổ xung vào cây khung. Đối với đồ thị cỡ m cạnh thì  cần phải thực hiện cỡ m*logm phép toán để sắp xếp. Tuy nhiên, để xây dựng cây khung nhỏ nhất với n-1 cạnh, ta không cần sắp xếp toàn bộ mà chỉ cần xét phần trên cảu dãy đó. Để làm việc đó ta có thể sử dụng các thủ tục sắp xếp vun đống (Heap sort).

Trong thuật toán Kruskal việc lựa chọn cạnh để bổ xung đòi hỏi phải có một thủ tục hiệu quả đế kiểm tra tập cạnh T ∪ { e } có chứa chu trình hay không. Chú ý, các cạnh trong T ở bước lặp trung gian sẽ tạo thành một rừng. Cạnh e cần khảo sát sẽ tạo thành chu trình với các cạnh trong T khi và chỉ khi cả hai đỉnh đầu của nó thuộc cùng một cây con trong rừng nói trên. Do đó thêm cạnh e vào T không tạo thành chu trình khi và chỉ khi nó phải nối 2 cây khác nhau trong T. Một trong những phương pháp hiệu quả để thực hiện việc kiểm tra này là phân hoạch các đỉnh của đồ thị thành các tập con không giao nhau.

Chẳng hạn với đồ thị sau

kruskal

Ta có tập con có 6 tập con 1 phần tử: {1},{2},{3},{4},{5},{6}. Sau khi bổ xung cạnh có độ dài nhỏ nhất {3,5} ta có các tập con : {1},{2},{3,5},{4},{6}. Tiếp theo ta thêm cạnh {4,6} ta được các tập con {1},{2},{3,5},{4,6}. Tiếp theo ta thêm canh {4,5} ta được các tập con {1},{2},{3,5,4,6}. Cạnh có độ dài tiếp theo là {5,6} nhưng do hai đầu của nó thuộc cùng một tập con {3,5,4,6} nên cạnh {5,6} không được chọn.

Chương trình tìm cây khung nhỏ nhất theo thuật toán Kruskal được thể hiện như sau:

#include<iostream>

#include<conio.h>

using namespace std;

#define MAX 50

#define TRUE 1

#define FALSE  0

int n, m, minl, connect;

int dau[500], cuoi[500], w[500];//mảng chứa đỉnh đầu, cuối và độ dài các cạnh của đồ thị.

int daut[50], cuoit[50], father[50];

void Init(void){

 freopen("baotrum.in", "r",stdin);

 cin>>n>>m;

 cout<<"So dinh do thi: "<< n <<endl;

 cout<<"So canh do thi:" << m <<endl;

 //nhập danh sách kề

 for (int i = 1; i <= m; i++){

  cin>>dau[i]>>cuoi[i]>>w[i];

 }

}

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 last, u, v, r1, r2, ncanh, ndinh;

 for (int i = 1; i <= n; i++)

  father[i] = -1;

 //sử dụng thuật toán vun đống để sắp xếp các cạnh của đồ thị theo thứ tự không giảm của độ dài.

 for (int i = m / 2; i > 0; i--)

  Heap(i, m);

 

 last = m; ncanh = 0; ndinh = 0; minl = 0; connect = TRUE;

 //Lựa chọn cạnh bổ xung vào cây khung.

 while (ndinh < n - 1 && ncanh < m){

  ncanh = ncanh + 1;

  u = dau[1];

  v = cuoi[1];

  //tìm gốc của phân hoạch 1.

  r1 = Find(u);

  //tìm gốc của phân hoạch 2.

  r2 = Find(v);

  if (r1 != r2) {//nếu hai gốc khác nhau thì cạnh đang xét có thể thêm được vào đồ thị.

   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){

 cout<<"Do dai cay khung nho nhat:"<< minl<<endl;

 cout<<"Cac canh cua cay khung nho nhat:"<<endl;

 for (int i = 1; i < n; i++)

  cout<< daut[i]<<" "<<cuoit[i]<<endl;

}

void main(void){

 Init();

 Krusal();

 Result();

 getch();

}

Ma trận liền kề baotrum.in

6  9
1  2  33
1  3  17
2  4  20
2  3  18
3  4  16
3  5  4
4  5  9
4  6  8
5  6  14

Output của chương trình.

So dinh: 6

So canh: 9

Do dai ngan nhat: 56

Cac canh cua cay khung nho nhat

3  5

4  6

4  5

1  3

2  3

Bạn thấy bài viết này như thế nào?: 
Average: 10 (2 votes)
Ảnh của Tommy Tran

Tommy Tran owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Cardapio – Thanh menu tuyệt vời cho Ubuntu 11.04

Cardapio – Thanh menu tuyệt vời cho Ubuntu 11.04

Trên bài viết trước mình đã hướng dẫn các bạn sử dụng menu kiểu của trên Unity, còn trong bài viết này, mình xin giới thiệu một tiện ích khác giúp bạn đem thanh menu...

Nữ tiến sĩ xinh đẹp tuyển người yêu về ăn Tết

Nữ tiến sĩ xinh đẹp tuyển người yêu về ăn Tết

Học thức cao lại có ngoại hình ưa nhìn, ăn mặc đẹp, thế nhưng vẫn có rất nhiều người ‘chê’ mỹ nữ tiến sĩ.

Rò rỉ thông số kĩ thuật của máy ảnh Sony Cyber-shot RX100 MkII

Rò rỉ thông số kĩ thuật của máy ảnh Sony Cyber-shot RX100 MkII

Sau khi tung ra Cyber-shot RX100 cách đây không lâu, có vẻ như Sony muốn tiếp tục gây ấn tượng với người dùng với kế hoạch phát hành Cyber-shot RX100 MkII.