Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Bài 4. Tìm Cây Phụ Tối Tiểu (Thuật Toán PRIM)

Share

ztanzzthanhz
Trung cấp
Trung cấp

Tổng số bài gửi : 60
Points : 100
Join date : 13/11/2009
Age : 26
Đến từ : Bến Tre

Bài 4. Tìm Cây Phụ Tối Tiểu (Thuật Toán PRIM)

Bài gửi  ztanzzthanhz on Mon Dec 14, 2009 11:58 pm

Tìm Cây Phụ Tối Tiểu


Bài làm sau em có xét luôn cả trường hợp không liên thông thì báo lỗi! cho nên hơi dài Very Happy

Code:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <values.h>
#define fi "D:\\PRIM.INP"
#define fo "D:\\PRIM.OUT"

int    error=0,
   V, dd[100],
   G[100][100];
   KQ[100][100];

void input(){
   FILE *f;
   int s;
   f = fopen(fi,"r");

   if (f!=NULL){
      if (fscanf(f,"%d\n",&s))
         V=s;
      else {error=1; exit;}
      for (int i=0; i<V; i++){
         for (int j=0; j<V; j++)
            if (fscanf(f,"%d",&s))
               G[i][j]=s;
            else {error=1; exit;}
         fscanf(f,"\n");
      }
   }
   else error=1;
   fclose(f);
}
void init(){
   for (int i=0; i<100; i++){
      dd[i]=0;
      for (int j=0; j<100; j++)
         KQ[i][j]=0;
   }
}
void xuly(){
   int min = MAXINT, x, y;
   for (int i=0; i<V; i++)
   for (int j=0; j<V; j++)
      if ((G[i][j]>0)&&(G[i][j]<min)){
         x=i;
         y=j;
         min=G[x][y];
      }

   KQ[x][y]=G[x][y];
   KQ[y][x]=G[y][x];
   dd[x]=1;
   dd[y]=1;
   for (int s=2; s<V; s++){
      min = MAXINT;
      for (i=0; i<V; i++)
      for (j=0; j<V; j++)
         if ((G[i][j])&&(G[i][j]<min)&&(dd[i])&&(!dd[j])){
         x=i;
         y=j;
         min=G[x][y];
      }
      KQ[x][y]=G[x][y];
      KQ[y][x]=G[y][x];
      dd[x]=1;
      dd[y]=1;
   }
}
void output(){
   FILE *f;
   f = fopen(fo,"w");
   fprintf(f,"%d\n",V);
   for (int i=0; i<V; i++){
      for (int j=0; j<V; j++)
         fprintf(f,"%3d",KQ[i][j]);
      fprintf(f,"\n");
   }
   fclose(f);
}
void BFS(){
   int stack[100], dinh, spt;
   dd[0]=1;
   stack[0]=0;
   spt=1;
   while (spt>0){
      spt--;
      dinh=stack[spt];
      for (int i=0; i<V; i++)
         if (G[dinh][i] &&  !dd[i]){
            dd[i]=1;
            stack[spt]=i;
            spt++;
         }
   }
}
int LienThong(){
   for (int i=0; i<V; i++)
      dd[i]=0;
   BFS();
   for (i=0; i<V; i++)
      if (!dd[i])
         return 0;
   return 1;
}

void main(){
   input();
   clrscr();
   if (!error){
      if (LienThong()){
         init();
         xuly();
         output();
      }
      else{
         printf("\n\nDo thi khong LIEN THONG lam sao co cay phu toi tieu?");
         getch();
      }
   }
   else{
      printf("\n\nLoi khong tim thay file input hoac noi dung file input sai cu phap");
      getch();
   }
}

File input mẫu:
Code:

6
 0 10  0  0  0 30
10  0 50 20  0 50
 0 50  0 30  0  0
 0 20 30  0 40 70
 0  0  0 40  0 60
30 50  0 70 60  0
Mong quý thầy cô góp ý thêm cho em! Razz
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 36
Đến từ : Cần Thơ

Ứng dụng thuật toán Prim

Bài gửi  admin on Sat Dec 19, 2009 12:53 pm

Ứng dụng thuật toán Prim


Một công ty cần thay toàn bộ hệ thống dây điện cho n phòng làm việc. Cho biết sơ đồ điện hiện có của n căn phòng này được biều diễn bằng ma trận A[i,j] trong đó:
- A[i,j]=A[j,i] chính là chiều dài dây điện nối liền giữa hai phòng i và j.
- A[i,j] = A[j,i] = 0 nếu i không nối liền với j.
Hãy lập trình tính độ dài cuả dây dẫn cần sử dụng sao cho cả n phòng điều có điện và số lượng này là ít nhất.
Chú ý: đồ thị đã cho là liên thông.
Dữ liệu vào: cho trong file Bai8.inp (đồ thị cho đã liên thông).
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0- Dòng i+1 (1<= i <= n) chứa n số A[i,1],A[i,2]…A[i,n] mỗi số cách nhau bởi một khoảng trắng.
Dữ liệu ra: lưu trong file Bai8.out với nội dung sau:
- Dòng đầu lưu độ dài dây dẫn nhỏ nhất
- Các dòng còn lại lưu đường đi cần nối điện giữa đỉnh i nối với đỉnh j có trọng số A[i,j] (i -> j = A[i][j]).

Bai8.inp
5
0 3 3 2 2
3 0 2 3 8
3 2 0 1 4
2 3 1 0 4
2 8 4 4 0

Bai8.out
7
4 – 3
3 – 2
4 – 1
1 – 5

Bai8.inp
8
0 2 3 4 0 0 0 0
2 0 3 0 4 0 0 0
3 3 0 7 6 5 2 0
4 0 7 0 0 0 3 0
0 4 6 0 0 4 0 8
0 0 5 0 4 0 1 6
0 0 2 3 0 1 0 5
0 0 0 0 8 6 5 0

Bai8.out
20
1 - 2
1 - 3
3 - 7
7 - 6
7 - 4
2 - 5
7 - 8

Thuật toán Prim tìm cây phủ tối tiểu.
Bước 1: Xuất phát từ đỉnh k bất kỳ (thông thường chọn đỉnh đầu tiên) chọn một cạnh có trọng số nhỏ nhất liền kề với đỉnh k (min{A[k][j]}j=1..n) ta đánh dấu 2 đỉnh đi qua cạnh đó
và số cạnh tìm được là 1. Chuyển sang bước 2.
Bước 2: Tìm cạnh nhỏ nhất của đồ thị với điều kiện cạnh tìm được phải có 1 đỉnh chưa đánh dấu và 1 đỉnh đã đánh dấu (min{A[i][j]}j=1..n, i=1..n sao cho i đánh đấu và j chưa đánh dấu) để tránh trường hợp tạo thành chu trình. Ta tăng số cạnh tìm được lên 1 và chuyển sang bước 3.
Bước 3: Nếu số cạnh tìm được bằng n-1 kết thúc thuật toán, ngược lại quay về bước 2.

HƯỚNG DẪN CÀI ĐẶT
Ta tổ chức mảng 1 chiều D để đánh dấu . Nếu D[i]=1 đỉnh i được đánh dấu và D[i]=0 nếu i chưa được đánh dấu.
Bước 1: Tìm min{A[1][j]}j=1..n. Sau đó gán D[1]=D[j]=1 (đánh dấu 2 đỉnh 1,j) và cho số cạnh tìm được bằng 1 (Dem=1).
Bước 2: Tìm min{A[i][j]}j=1..n, i=1..n với điều kiện D[i]=1 và D[j]=0. Sau đó gán D[j]=1 (đánh dấu đỉnh j vừa tìm được) và tăng số cạnh lên 1 (Dem++).
Bước 3: Nếu Dem = n-1 thì thuật toán kết thúc.

Code:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <values.h>
#define FileInt "Bai8.inp"
#define FileOut "Bai8.out"

/*Lưu lại những cạnh đã đi qua x->y*/
typedef struct Egde {
   int x,y;
};
/*Doc dữ liệu từ file*/
void Doc_File(int **A,int &n){
   FILE*f = fopen(FileInt,"rb");
   fscanf(f,"%d",&n);
   *A = new int [n];
   for(int i =0;i<n;i++) {
      A[i] = new int [n];
      for(int j =0;j<n;j++) {
         fscanf(f,"%d",&A[i][j]);
      }
   }
   fclose(f);
}
/*Ghi dữ liệu ra file*/
void Ghi_File(Egde*L,int n,int Sum) {
   FILE*f = fopen(FileOut,"wb");
   fprintf(f,"%d\n",Sum);
   for(int i =0; i<n-1; i++)
      fprintf(f,"%d - %d\n",L[i].x+1,L[i].y+1);
   fclose(f);
}
/*Thuật toán Prim*/
void Prim(int **A, int n){
   char *D = new char[n];    /*Dánh dấu đỉnh*/
   Egde *L = new Egde[n-1];    /*Lưu đường đi */
   int min = MAXINT, Dem = 0, Sum = 0;
   /*Khoi tạo giá trị cho mảng đánh dấu*/
   for(int i=0; i<n; i++)
      D[i]=0;
   /*Tìm cạnh nhỏ nhất đầu tiên xuất phát từ đỉnh 1*/
   for(int j=1; j<n; j++)
   if(min>A[0][j] && A[0][j]!=0){
      min = A[0][j];
      L[0].y = j;
   }
   L[0].x = 0;
   D[0] =    D[L[0].y] = 1;
   Sum+=min;
   Dem++;
   /*Thực hiện cho đến khi số cạnh tìm được là n-1 cạnh*/
   do{
      min = MAXINT;
      for( i=0; i<n; i++)
      if(D[i]==1)
      for( j=0; j<n; j++)
      if(A[i][j]>0 && min>A[i][j] && D[j]==0){
            min = A[i][j];
            L[Dem].x = i;
            L[Dem].y = j;
      }
      Sum+=min;
      D[L[Dem].y] = 1;
      Dem++;
   } while(Dem<n-1);
   Ghi_File(L,n,Sum);       /*Ghi kết quả tìm được vào file*/
}
/*Chương trình chính*/
void main() {
   int **A,n;
   Doc_File(A,n);
   Prim(A,n);
   delete *A;
}

YoYoHomeZone
Nhập môn
Nhập môn

Tổng số bài gửi : 2
Points : 2
Join date : 07/09/2010

Re: Bài 4. Tìm Cây Phụ Tối Tiểu (Thuật Toán PRIM)

Bài gửi  YoYoHomeZone on Tue Sep 07, 2010 9:50 am

Ui, bài này debug bằng Visual Studio 2005 thì làm sao nhỉ? Giúp mình với, đang cần gấp. hu hu hu
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 36
Đến từ : Cần Thơ

Re: Bài 4. Tìm Cây Phụ Tối Tiểu (Thuật Toán PRIM)

Bài gửi  admin on Wed Feb 16, 2011 8:31 am

YoYoHomeZone đã viết:Ui, bài này debug bằng Visual Studio 2005 thì làm sao nhỉ? Giúp mình với, đang cần gấp. hu hu hu

Ngôn ngữ thì cũng vậy chỉ khác cách khai báo mảng và dữ liệu đầu vào thôi. Bạn nghiên cứu thêm về mảng và cấu trúc tập tin là ok.
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 36
Đến từ : Cần Thơ

Cải tiến thuật toán Prim

Bài gửi  admin on Thu Oct 11, 2012 3:47 pm

Code:
void Prim(int **A, int n){
   char *D = new char[n];
   Egde *L = new Egde[n-1];
   int min = MAXINT, Dem = 0, Sum = 0;
   for(int i=0; i<n; i++)
      D[i]=0;
   D[0] = 1;
   do{
      min = MAXINT;
      for( i=0; i<n; i++)
      {
         if(D[i]==1)
         {
            for(int j=0; j<n; j++)
               if(A[i][j]>0 && min>A[i][j] && D[j]==0)
               {
                     min = A[i][j];
                     L[Dem].x = i;
                     L[Dem].y = j;
               }
         }
      }
      Sum+=min;
      D[L[Dem].y] = 1;
      Dem++;
   } while(Dem<n-1);
   Ghi_File(L,n,Sum);
}


Gia sư Alpha
------------------------------------------------------------------------------------
Điện thoai: 07106 255 599 - 0932 836 026 - 0987 700 288
Website: http://giasualpha.com
Email: giasualpha@gmail.com
------------------------------------------------------------------------------------

Sponsored content

Re: Bài 4. Tìm Cây Phụ Tối Tiểu (Thuật Toán PRIM)

Bài gửi  Sponsored content


    Hôm nay: Mon Nov 20, 2017 4:25 pm