Hướng dẫn code kiểm tra đồ thị có hợp lệ và vô hướng hay có hướng không

Trong bài viết này chúng ta sẽ cùng tìm hiểu một số bài tập về đồ thị mời các bạn xem ngay bên dưới.

Hướng dẫn code kiểm tra đồ thị có hợp lệ và vô hướng hay có hướng không

1. Khai báo kiểu cấu trúc có tên đồ thị

#include <stdio.h>
#define MAX 100
struct DoThi{
int n;
int a[MAX][MAX];
};

2. Hàm đọc đồ thị từ file text trong máy tính

void DocDoThi(char *s, DoThi &g){
FILE *f;
f = fopen(s,”rt”);
if(f==NULL){
printf(“Khong tim thay tap tin”);
return;
}
fscanf(f,”%d”,&g.n);
for(int i=0; i<g.n;i++)
for(int j=0; j<g.n; j++)
fscanf(f,”%d”,&g.a[i][j]);
}

3. Xuất đồ thị

void XuatDoThi(DoThi g){
printf(“\n %d”,g.n);
for(int i=0; i<g.n; i++){
printf(“\t”);
for(int j=0; j<g.n;j++)
printf(“%d “,g.a[i][j]);
printf(“\n”);
}
}

4. Kiểm tra đồ thị đơn có hợp lệ hay không

Đồ thị đơn hợp lệ là đồ thị có đường chéo chính bằng 0 và ngược lại

int KiemTraDoThiDon(DoThi g){
for(int i=0; i<g.n; i++){
if(g.a[i][i] != 0){
return 0;
return 1;
}
}
}

5. Kiểm tra đồ thị đơn là vô hướng hay có hướng

Đồ thi đơn vô hướng là đồ thị có giá trị cạnh a[i][j] = a[j][i]
Đồ thì đơn có hướng là độ thị có giá trị cạnh a[i][j] != a[j][i]

int KiemTraDoThiDonVoHuong(DoThi g){
for(int i=0;i<g.n; i++){
for(int j=0;j<g.n;j++)
if(g.a[i][j] != g.a[j][i])
return 0;
return 1;
}
}

Toàn bộ code

#include <stdio.h>
#define MAX 100
struct DoThi{
int n;
int a[MAX][MAX];
};
void DocDoThi(char *s, DoThi &g);
void XuatDoThi(DoThi g);
int KiemTraDoThiDon(DoThi g);
int KiemTraDoThiDonVoHuong(DoThi g);
int main(){
DoThi g;
do{
printf(“\n 0: Thoat”);
printf(“\n 1: Doc do thi”);
printf(“\n 2: Xuat do thi”);
printf(“\n 3: Kiem tra do thi don”);
printf(“\n 4: Kiem tra do thi vo huong”);
int chon;
printf(“\n Lua chon chuc nang:”);
scanf(“%d”,&chon);
if(chon==0) return 0;
if(chon==1){
char diachitaptin[30];
printf(“\n Nhap duong dan:”);
scanf(“%s”,diachitaptin);
DocDoThi(diachitaptin,g);
}
if(chon==2){
printf(“\n Do thi la:”);
XuatDoThi(g);
}
if(chon==3){
if(KiemTraDoThiDon(g))
printf(“\n Do thi hop le”);
else
printf(“\n Do thi khong hop le”);
}
if(chon==4){
if(KiemTraDoThiDonVoHuong(g))
printf(“\n Day la do thi vo huong”);
else
printf(“\n Day la do thi co huong”);
}
printf(“\n Nhap lai menu”);
}while(1);
return 0;
}
void DocDoThi(char *s, DoThi &g){
FILE *f;
f = fopen(s,”rt”);
if(f==NULL){
printf(“Khong tim thay tap tin”);
return;
}
fscanf(f,”%d”,&g.n);
for(int i=0; i<g.n;i++)
for(int j=0; j<g.n; j++)
fscanf(f,”%d”,&g.a[i][j]);
}
void XuatDoThi(DoThi g){
printf(“\n %d”,g.n);
for(int i=0; i<g.n; i++){
printf(“\t”);
for(int j=0; j<g.n;j++)
printf(“%d “,g.a[i][j]);
printf(“\n”);
}
}
int KiemTraDoThiDon(DoThi g){
for(int i=0; i<g.n; i++){
if(g.a[i][i] != 0){
return 0;
return 1;
}
}
}
int KiemTraDoThiDonVoHuong(DoThi g){
for(int i=0;i<g.n; i++){
for(int j=0;j<g.n;j++)
if(g.a[i][j] != g.a[j][i])
return 0;
return 1;
}
}