Tâm đồ thị

Bai thuc hanh tuan 13:

Xet do thi co trong so G = (V, E, W).

Input: file Graph.INP chua thong tin ve ma tran trong so cua do thi G, co cau truc nhu sau:

- dong dau ghi so dinh N cua do thi

- N dong tiep theo, moi dong la 1 hang cua ma tran trong so

Yeu cau: Doc ma tran trong so vao bo nho dong, tim tam va duong kinh cua G.

Tim duong di ngan nhat noi giua tam va cac dinh khac tam.

Output: Ghi ket qua ra tep ShortestPath.OUT theo cau truc nhu sau:

Dong dau tien ghi tam va duong kinh cua G.

Cac dong tiep theo moi dong ghi mot dinh khac tam

va duong di ngan nhat tu tam toi dinh do.

*/

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#define VoCung 1000

// Ham doc du lieu tu file van ban co san

int *DocDuLieu(int *Mtr,int *n)

{

FILE *f;

int t;

f=fopen("Graph.INP","r");

if(!f)

{

printf("

\tLoi mo file");

getch();

exit(0);

}

fscanf(f,"%d",n);

Mtr=(int *)calloc((*n)*(*n),sizeof(int));

if(!Mtr)

{

printf("

\tLoi cap phat");

getch();

exit(0);

}

for(int i=0;i<(*n)*(*n);i++)

{

fscanf(f,"%d",&t);

*(Mtr+i)=t;

}

fclose(f);

return Mtr;

}

// Khoi tao cho mang TruyVet

int *KhoiTao(int *TruyVet,int n)

{

TruyVet=(int *)calloc(n*n,sizeof(int));

if(!TruyVet)

{

printf("

\tLoi cap phat");

getch();

exit(0);

}

for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

*(TruyVet+i*n+j)=i;

return TruyVet;

}

// Su dung thuat toan Floyd de duyet do thi

void Floyd(int *Mtr,int n,int *TruyVet)

{

for(int k=0;k<n;k++)

for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

if( *(Mtr+i*n+j) > (*(Mtr+i*n+k) + *(Mtr+k*n+j)) )

{

*(Mtr+i*n+j)=*(Mtr+i*n+k) + *(Mtr+k*n+j);

*(TruyVet+i*n+j)=*(TruyVet+k*n+j);

}

}

// mang d[] luu do lech cua cac dinh trong do thi, ham tinh do lech cua cac dinh trong do thi

void DoLech(int n,int *TruyVet,int *Mtr,int d[100])

{

for(int i=0;i<n;i++)

{

d[i]=0; // gia su do lech cua dinh i bang 0

for(int j=0;j<n;j++)

if(d[i]<*(Mtr+i*n+j))

d[i]=*(Mtr+i*n+j);

}

}

// ham tra lai dinh la tam cua do thi

int TimTam(int n,int d[100])

{

int tam=1;

for(int i=0;i<n;i++)

if(d[tam]>d[i])

tam=i;

return tam;

}

// ham tinh duong kinh cua do thi

int TinhDuongKinh(int n,int *Mtr)

{

int dkinh=*Mtr;

for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

if(dkinh<*(Mtr+i*n+j))

dkinh=*(Mtr+i*n+j);

return dkinh;

}

// ham ghi file output

void GhiFile(int n,int *TruyVet,int d[100],int *Mtr)

{

FILE *f;

f=fopen("ShortestPath.OUT","w");

if(!f)

{

printf("

\tLoi mo file");

getch();

exit(0);

}

DoLech(n,TruyVet,Mtr,d);

int tam=TimTam(n,d),dkinh=TinhDuongKinh(n,Mtr);

fprintf(f,"%d",tam);

fprintf(f," %d",dkinh);

fprintf(f,"

");

int temp;

for(int i=0;i<n;i++)

if(i!=tam)

{

temp=i;

fprintf(f,"%d: ",temp);

fprintf(f,"%d",temp);

while(temp!=tam)

{

fprintf(f,"<-%d",*(TruyVet+tam*n+temp));

temp=*(TruyVet+tam*n+temp);

}

fprintf(f,"

");

}

fclose(f);

}

int main()

{

int *Mtr,n,*TruyVet,d[100];

/* *Mtr dung de luu ma tran trong so cua do thi, n la so dinh cua do thi */

Mtr=DocDuLieu(Mtr,&n);

TruyVet=KhoiTao(TruyVet,n);

Floyd(Mtr,n,TruyVet);

GhiFile(n,TruyVet,d,Mtr);

getch();

return 0;

}

Bạn đang đọc truyện trên: AzTruyen.Top

Tags: #hành