Search
Latest topics
Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS
Page 1 of 1
Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS
- 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();
}
Link:http://www.mediafire.com/?3mddjnt4mtm
Similar topics
» Ứng dụng thuật toán Prim
» Một số thuật ngữ tin học thông dụng
» Thuật toán QuickSort
» Thuật toán Dijkstra
» Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất
» Một số thuật ngữ tin học thông dụng
» Thuật toán QuickSort
» Thuật toán Dijkstra
» Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum
Thu Aug 23, 2012 5:38 am by Admin
» Tuyệt kỹ cua giai
Thu Aug 23, 2012 5:36 am by Admin
» NETCAT.........
Mon Aug 13, 2012 6:35 am by Admin
» Bảo mật CSDL bằng phương pháp mã hóa.
Tue Apr 17, 2012 10:04 pm by Admin
» Hàm mã hóa MD5 bằng JavaScript
Tue Apr 17, 2012 10:03 pm by Admin
» Giá của món quà
Fri Apr 13, 2012 6:01 am by Admin
» Sẽ chỉ yêu ai?
Fri Apr 13, 2012 6:01 am by Admin
» Cách đọc bảng chữ cái!
Thu Apr 12, 2012 10:37 pm by Admin
» Gắn trojan, keylog, virus vào website, forum
Tue Apr 10, 2012 1:14 am by Admin