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: 9.1 (10 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: [email protected]
  • Telegram Messenger: https:/t.me/tommytran0401

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

 
Kỹ thuật Reviewing Code với IDE PHPStorm to inspect code

Kỹ thuật Reviewing Code với IDE PHPStorm to inspect code

This process can be overkill for a one line patch, but once the patch is more than a couple of lines is helps the reviewer a great deal.

5 cách để copywriter cần làm đối với Google

5 cách để copywriter cần làm đối với Google

Nội dung là phần không thể thiếu trong mỗi website, đặc biệt là khi thực hiện các chiến dịch SEO đòi hỏi lượng nội dung chất lượng.

CNN điều tra nhà máy Foxconn - Phỏng vấn công nhân lắp ráp iPad tại Trung Quốc

CNN điều tra nhà máy Foxconn - Phỏng vấn công nhân lắp ráp iPad tại Trung Quốc

Mặc cho Apple và Foxconn luôn khẳng định bảo vệ người lao động, hiện thực có vẻ hoàn toàn trái ngược.

Wordpress Freelancer

 

Wordpress Freelancer