09HCB
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

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  

 

 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