Bài tự viết, vì vậy nếu có sai sót cũng là chuyện bình thường, mong thầy cô và các bạn góp ý thêm!
Download: http://www.mediafire.com/?3mddjnt4mtm
Down về, giải nén ra, move file "LTHONG.INP" vào thư mục gốc ổ "D:\". Còn file "LTHONG.CPP" để đâu cũng được. Mở file "LTHONG.CPP" bằng C++ và chạy chương trình.
Muốn thay đổi dữ liệu vào thì chỉnh sửa trong file "LTHONG.INP" theo cú pháp:
(Chú ý: sửa sai cú pháp hoặc sai đường dẫn file input chương trình sẽ báo lỗi)
Mọi chi tiết xin liên hệ: Dương Tấn Thành - Lớp CNTT1 K9 - http://cntt1k9.info
Hoặc reply tại bài viết này!
Code:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define fi "D:\\LTHONG.INP"
int error=0,
V, dd[100],
G[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 DFS(){
int quene[100], top=0, bottom=0, dinh;
dd[0]=1;
quene[0]=0;
while (bottom<=top){
dinh=quene[bottom];
for (int i=0; i<V; i++)
if (G[dinh][i] && !dd[i]){
dd[i]=1;
top++;
quene[top]=i;
}
bottom++;
}
}
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;
//Chon 1 trong 2, DFS hoac BFS
DFS();
//BFS();
for (i=0; i<V; i++)
if (!dd[i])
return 0;
return 1;
}
void main(){
clrscr();
input();
if (!error)
if (LienThong())
printf("\n\nDo thi lien thong");
else
printf("\n\nDo thi khong lien thong");
else
printf("\n\nLoi khong tim thay file input hoac noi dung file input sai cu phap");
getch();
}
Download: http://www.mediafire.com/?3mddjnt4mtm
Down về, giải nén ra, move file "LTHONG.INP" vào thư mục gốc ổ "D:\". Còn file "LTHONG.CPP" để đâu cũng được. Mở file "LTHONG.CPP" bằng C++ và chạy chương trình.
Muốn thay đổi dữ liệu vào thì chỉnh sửa trong file "LTHONG.INP" theo cú pháp:
- Dòng đầu là 1 số nguyên V (số đỉnh của đồ thị)
- V dòng tiếp theo, mỗi dòng gồm V số (0 hoặc 1). Là ma trận G. Với G[u][v] = 0 nếu từ đỉnh u không có đường đi trực tiếp đến đỉnh v, và ngược lại.
(Chú ý: sửa sai cú pháp hoặc sai đường dẫn file input chương trình sẽ báo lỗi)
Mọi chi tiết xin liên hệ: Dương Tấn Thành - Lớp CNTT1 K9 - http://cntt1k9.info
Hoặc reply tại bài viết này!