zztanzzthanhzz Thành viên cấp 2
Tổng số bài gửi : 126 Join date : 17/07/2009 Age : 33 Đến từ : CNTT1 K9
| Tiêu đề: Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS Sun Dec 13, 2009 5:24 am | |
| | | | | Bài tự viết, vì vậy nếu có sai sót cũng là chuyện bình thường há các bạn! Mong các bạn góp ý thêm! - 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! | | | | |
|
|
cutuan527 Moderators
Tổng số bài gửi : 1051 Join date : 26/04/2009 Age : 33 Đến từ : Vĩnh Long
| Tiêu đề: Re: Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS Sun Dec 13, 2009 8:21 am | |
| |
|
caingocthanh Moderators
Tổng số bài gửi : 559 Join date : 27/04/2009 Age : 35 Đến từ : Cà Mau
| Tiêu đề: Re: Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS Sun Dec 13, 2009 9:38 am | |
| |
|
zztanzzthanhzz Thành viên cấp 2
Tổng số bài gửi : 126 Join date : 17/07/2009 Age : 33 Đến từ : CNTT1 K9
| Tiêu đề: Re: Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS Sun Dec 13, 2009 3:04 pm | |
| |
|
Sponsored content
| Tiêu đề: Re: Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS | |
| |
|