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++

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++

Bài toán tìm cây bao trùm nhỏ nhất là một trong những bài toán tối ưu trên đồ thị có ứng dụng trong nhiều lĩnh vực khác nhau của thực tế. Bài toán được phát biểu như sau:
Cho G=<V, E>là đồ thị vô hướng liên thông với tập đỉnh V = {1, 2,..., n }và tập cạnh E gồm m cạnh. Mỗi cạnh e của đồ thị được gán với một số không âm c(e) được gọi là độ dài của nó. Giả sử H=<V, T>là một cây bao trùm của đồ thị G. Ta gọi độ dài c(H) của cây bao trùm H là tổng độ dài các cạnh: c(H) = SUM(c(e)). Bài toán được đặt ra là, trong số các cây khung của đồ thị hãy tìm cây khung có độ dài nhỏ nhất của đồ thị.

Để minh họa cho những ứng dụng của bài toán này, chúng ta có thể tham khảo hai mô hình thực tế của bài toán.

Bài toán nối mạng máy tính. Một mạng máy tính gồm n máy tính được đánh số từ 1, 2,..., n. Biết chi phí nối máy i với máy j là c[i, j], i, j = 1, 2,..., n. Hãy tìm cách nối mạng sao cho chi phí là nhỏ nhất.

Bài toán xây dựng hệ thống cable. Giả sử ta muốn xây dựng một hệ thống cable điện thoại nối n điểm của một mạng viễn thông sao cho điểm bất kỳ nào trong mạng đều có đường truyền tin tới các điểm khác. Biết chi phí xây dựng hệ thống cable từ điểm i đến điểm j là c[i,j]. Hãy tìm cách xây dựng hệ thống mạng cable sao cho chi phí là nhỏ nhất.

Để giải bài toán cây bao trùm nhỏ nhất, chúng ta có thể liệt kê toàn bộ cây bao trùm và chọn trong số đó một cây nhỏ nhất. Phương án như vậy thực sự không khả thi vì số cây bao trùm của đồ thị là rất lớn cỡ n^n-2, điều này không thể thực hiện được với đồ thị với số đỉnh cỡ chục.

Để tìm một cây bao trùm chúng ta có thể thực hiện theo các bước như sau:

  • Bước 1.Thiết lập tập cạnh của cây bao trùm là φ. Chọn cạnh e = (i, j)có độ dài nhỏ nhất bổ sung vào T.
  • Bước 2. Trong số các cạnh thuộc E \ T, tìm cạnh e = (i1, j1)có độ dài nhỏ nhất sao cho khi bổ sung cạnh đó vào T không tạo nên chu trình. Để thực hiện điều này, chúng ta phải chọn cạnh có độ dài nhỏ nhất sao cho hoặc i1∈Tvà j1∉T, hoặc j1∈Tvà i1∉T
  • Bước 3. Kiểm tra xem T đã đủ n-1 cạnh hay chưa? Nếu T đủ n-1 cạnh thì nó chính là cây bao trùm ngắn nhất cần tìm. Nếu T chưa đủ n-1 cạnh thì thực hiện lại bước 2. 

Ví dụ. Tìm cây bao trùm nhỏ nhất của đồ thị trong hình:

thuat toan cay bao trum

Bước 1. Đặt T=φ. Chọn cạnh (3, 5) có độ dài nhỏ nhất bổ sung vào T.

Buớc 2. Sau ba lần lặp đầu tiên, ta lần lượt bổ sung vào các cạnh (4,5), (4, 6). Rõ ràng, nếu bổ sung vào cạnh (5, 6) sẽ tạo nên chu trình vì đỉnh 5, 6 đã có mặt trong T. Tình huống tương tự cũng xảy ra đối với cạnh (3, 4) là cạnh tiếp theo của dãy. Tiếp đó, ta bổ sung hai cạnh (1, 3), (2, 3) vào T.

Buớc 3. Tập cạnh trong T đã đủ n-1 cạnh: T={ (3, 5), (4,6), (4,5), (1,3), (2,3)} chính là cây bao trùm ngắn nhất.

Chương trình cài đặt:

#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 E1[MAX], E2[MAX], D[MAX], EB[MAX], V[MAX];

/*  E1  :  Lưu trữtập đỉnh

đầu của các cạnh;

E2  : Lưu trữtập đỉnh cuối của các cạnh;

D  : Độdài các cạnh;

EB  : Tập cạnh cây bao trùm ;

V  : Tập đỉnh của đồthịcũng là tập đỉnh của cây bao trùm;

*/

int i, k, n, m, sc, min, dai;

FILE *fp;

void Init(void){

 fp = fopen("BAOTRUM.IN", "r");

 if (fp == NULL){

  printf("\n Khong co file Input");

  getch(); return;

 }

 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 canh:");

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

  fscanf(fp, "%d%d%d", &E1[i], &E2[i], &D[i]);

  printf("\n%4d%4d%4d", E1[i], E2[i], D[i]);

 }

 fclose(fp);

 for (i = 1; i <= m; i++) EB[i] = FALSE;

 for (i = 1; i <= n; i++) V[i] = FALSE;

}

void STREE_SHORTEST(void){

 /* Giai đoạn 1 của thuật toán là tìm cạnh k có độdài nhỏnhất*/

 min = D[1]; k = 1;

 for (i = 2; i <= m; i++) {

  if (D[i] < min){

   min = D[i]; k = i;

  }

 }

 /* Kết nạp cạnh k vào cây bao trùm*/

 EB[k] = TRUE; V[E1[k]] = TRUE; V[E2[k]] = TRUE; sc = 1;

 do {

  min = 32000;

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

   if (EB[i] == FALSE && (

    ((V[E1[i]]) && (V[E2[i]] == FALSE)) ||

    ((V[E1[i]] == FALSE) && (V[E2[i]] == TRUE)))

    && (D[i] < min)){

    min = D[i]; k = i;

   }

  }

  /* Tìm k là cạnh nhỏnhất thỏa mãn điều kiện nếu kết nạp

  cạnh vào cây sẽkhông tạo nên chu trình*/

  EB[k] = TRUE; V[E1[k]] = TRUE; V[E2[k]] = TRUE; sc = sc + 1;

 } while (sc != (n - 1));

}

void Result(void){

 printf("\n Cay bao trum:");

 dai = 0;

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

  if (EB[i]){

   printf("\n Canh %4d %4d dai %4d", E1[i], E2[i], D[i]);

   dai = dai + D[i];

  }

 }

 printf("\n Do dai cay bao trum:%d", dai);

}

void main(void){

 Init();

 STREE_SHORTEST();

 Result();

 getch();

}
Bạn thấy bài viết này như thế nào?: 
Average: 10 (1 vote)
Ả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

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

 
Joomla Seo không tốt bằng Drupal 7

Joomla Seo không tốt bằng Drupal 7

Trong số các hệ quản trị nội dung (CMS) phổ biến hiện nay, nổi bật lên hai ứng viên sáng giá nhất là Joomla! và Drupal. Hai hệ quản trị nội dung này thay nhau làm mưa làm gió trong các cuộc thi. Đặc biệt ở cuộc bình chọn uy tín nhất của Packt Publishing, Joomla! và Drupal luôn chiếm giữ hai vị trí đầu bảng.

Giấy phép ICP [Bộ Thông tin & Truyền thông cấp] là gì?

Giấy phép ICP [Bộ Thông tin & Truyền thông cấp] là gì?

ICP là giấy phép cung cấp thông tin trên thiết lập trang tin điện tử trên Internet, nói nôm na là giấy phép mở trang web, được cấp theo Quyết định số 27/2002/QĐ-BVHTT ngày 10/10/2002 ban hành ban hành

Những xu hướng di động đáng chú ý năm 2013

Giới công nghệ thừa nhận 2013 là năm đặc biệt của smartphone bởi dòng sản phẩm này đã đạt được những thành tựu khác hẳn giai đoạn trước đó. Doanh số điện thoại thông minh đã lần đầu tiên vượt điện thoại cơ bản cũng như được trang bị những đặc điểm tưởng chừng còn xa vời như chip 64 bit hay nhận diện vân tay, nhận diện chuyển động...

Wordpress Freelancer

 

Wordpress Freelancer