09HCB

Trang chủ 09HCB- Lớp Hoàn Chỉnh Đại Học Khoá 2009-2011
 
Trang ChínhTrang Chính  GalleryGallery  Tìm kiếmTìm kiếm  Đăng kýĐăng ký  Đăng NhậpĐăng Nhập  

Share
 

 Prim ------------------

Go down 
Tác giảThông điệp
balo

balo

Tổng số bài gửi : 17
Join date : 16/03/2010

Prim ------------------ Empty
Bài gửiTiêu đề: Prim ------------------   Prim ------------------ Empty27/4/2010, 9:56 am

Về Đầu Trang Go down
canary

canary

Tổng số bài gửi : 52
Join date : 17/03/2010

Prim ------------------ Empty
Bài gửiTiêu đề: Re: Prim ------------------   Prim ------------------ Empty27/4/2010, 7:24 pm

Về Đầu Trang Go down
balo

balo

Tổng số bài gửi : 17
Join date : 16/03/2010

Prim ------------------ Empty
Bài gửiTiêu đề: BAI LAM DE THAM KHAO   Prim ------------------ Empty6/5/2010, 12:56 am

Code:
#include<conio.h>
#include<stdio.h>
#include<math.h>
#define vocuc 22222


typedef struct
{
int x;
int y;
}Point;

typedef struct
{
   int v1;
   int v2;
   double trongso;
}EGDE;

typedef struct
{
int nVer;
double **a;
Point *p;
EGDE *T;
double tongtrongsoT;
}Graph;

void DocToaDoDinh(Graph &g);
double KhoangCach2Point(Point a, Point b);
void MaTranKeTrongSo(Graph &g);
int Prim(Graph &g);
int TimCanhNhoNhat(Graph g, EGDE  &canh, int labels[]);
void xuatT(Graph g);
void main()
{
   Graph gp;
   DocToaDoDinh(gp);
   MaTranKeTrongSo(gp);
   xuatT(gp);
}

void xuatT(Graph g)
{
   FILE *f;
   f=fopen("primOutput.txt","wt");

   if(Prim(g)==0)
   {
      fprintf(f,"Do thi khong co cay khung");
   }
   else
   {
      fprintf(f,"Tong chieu dai tuyen duong: %lf",g.tongtrongsoT);
      fprintf(f,"\n");
      for(int i=0;i<g.nVer-1;i++)
      {
         fprintf(f,"%2d      %2d      %2lf",g.T[i].v1,g.T[i].v2,g.T[i].trongso);
         fprintf(f,"\n");
      }
   }
   fclose(f);
   
}


int TimCanhNhoNhat(Graph g, EGDE  &canh, int *labels)
{
canh.v1=-1;
for(int i=0;i<g.nVer;i++)
{
   if(labels[i]==1)
   {
      for(int j=0;j<g.nVer;j++)
      {
         if(labels[j]==0&&g.a[i][j] != vocuc)
            if(canh.v1==-1 || canh.trongso>g.a[i][j])
            {
               canh.v1=i;
               canh.v2=j;
               canh.trongso=g.a[i][j];
            }
      }
   }      
}
if(canh.v1==-1) return 0;
return 1;
}

int Prim(Graph &g)
{
   int dinh=0;
   EGDE canh;
   int *labels=new int [g.nVer];

   g.T=new EGDE [g.nVer];

   for(int i=0;i<g.nVer;i++)
      labels[i]=0;
   g.tongtrongsoT=0;
   //Xet dinh 0
   labels[0]=1;
   while(dinh<g.nVer-1)
   {
      if(TimCanhNhoNhat(g,canh,labels)==0)  return 0;
      g.T[dinh]=canh;
      labels[canh.v2]=1;
      g.tongtrongsoT=g.tongtrongsoT+canh.trongso;
      dinh++;
   }
   return 1;
}

double KhoangCach2Point(Point a, Point b)
{
   return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}

void MaTranKeTrongSo(Graph &g)
{
   //Khai bao ma tran ke
   g.a=new double *[g.nVer];
   for(int i=0;i<g.nVer;i++)
      g.a[i]=new double[g.nVer];

   for(int i=0;i<g.nVer;i++)
   {
      g.a[i][i]=vocuc;
      for(int j=i+1;j<g.nVer;j++)
         g.a[i][j]=g.a[j][i]=KhoangCach2Point(g.p[i],g.p[j]);
   }
}

void DocToaDoDinh(Graph &g)
{
   FILE *f;
   f=fopen("cities.txt","rt");
   fscanf(f,"%d",&g.nVer);
   //Khai bao ma tran Point
   g.p=new Point [g.nVer];

   for(int i=0; i<g.nVer; i++)
   {
      fscanf(f,"%d");
      fscanf(f,"%d",&g.p[i].x);
      fscanf(f,"%d",&g.p[i].y);
      fscanf(f,"\n");
   }
   fclose(f);
}

Về Đầu Trang Go down
ben313

ben313

Tổng số bài gửi : 13
Join date : 18/03/2010

Prim ------------------ Empty
Bài gửiTiêu đề: Re: Prim ------------------   Prim ------------------ Empty6/5/2010, 9:18 am

Ban balo co the post noi dung + tai lieu buoi hoc thuc hanh LTDT (06/05/2010).
Thanks!
Về Đầu Trang Go down
Admin
Admin
Admin

Tổng số bài gửi : 149
Join date : 15/03/2010

Prim ------------------ Empty
Bài gửiTiêu đề: Re: Prim ------------------   Prim ------------------ Empty6/5/2010, 2:05 pm

Nội dung buổi học:
>Thực hành thuật toán Dịjktra theo file hướng dẫn trên Moodle.
> Công bố 2 bài Prim và Kruskal là bài thi lấy điểm giữa kỳ
>Cuối kỳ không tổ chức thi thực hành mà làm đồ án với nội dung sẽ cho sau.
>Điểm đc chia như sau: Thực hành 4 điểm, gồm: giữa kỳ (1điểm) và cuối kỳ(3đ), có thể có điểm cộng, Lý thuyết 6đ.
Hết!
Về Đầu Trang Go down
https://09hcb.forumvi.com
ben313

ben313

Tổng số bài gửi : 13
Join date : 18/03/2010

Prim ------------------ Empty
Bài gửiTiêu đề: Re: Prim ------------------   Prim ------------------ Empty6/5/2010, 3:07 pm

thanks!
Về Đầu Trang Go down
Sponsored content




Prim ------------------ Empty
Bài gửiTiêu đề: Re: Prim ------------------   Prim ------------------ Empty

Về Đầu Trang Go down
 
Prim ------------------
Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
09HCB :: Lưu trữ :: HK1 :: LTDT-
Chuyển đến