Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS

Share

ztanzzthanhz
Trung cấp
Trung cấp

Tổng số bài gửi : 60
Points : 100
Join date : 13/11/2009
Age : 26
Đến từ : Bến Tre

Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS

Bài gửi  ztanzzthanhz on Mon Dec 14, 2009 2:05 am

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!
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: 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! Very Happy

qvluom
Sơ cấp
Sơ cấp

Tổng số bài gửi : 23
Points : 29
Join date : 26/11/2009

Re: Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS

Bài gửi  qvluom on Tue Dec 22, 2009 7:59 pm

Bài viết khá chi tiết, có hướng dẫn sử dụng. Tuy nhiên, lại không có phân tích giải thuật làm người đọc hơi khó hiểu. Bạn có vui lòng viết bài phân tích giải thuật cụ thể không?. Cám ơn

ztanzzthanhz
Trung cấp
Trung cấp

Tổng số bài gửi : 60
Points : 100
Join date : 13/11/2009
Age : 26
Đến từ : Bến Tre

Re: Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS

Bài gửi  ztanzzthanhz on Wed Dec 23, 2009 2:19 am

Trước tiên xin cám ơn qvluom đã quan tâm, đã đọc bài viết của em.

Về việc giải thích thuật toán này thì em e rằng không thể! vì em chỉ là 1 sinh viên, chưa có kinh nghiệm giảng dạy, không biết cách "nói sao cho người khác hiểu"! với lại nếu lỡ nói sai gì thì càng không tốt! nếu giữa 2 người với nhau, kêu em nói miệng cho người ta hiểu thì em còn có thể làm được! Very Happy

Vì thế việc giải thích thuật toán này đành để lại cho thầy đi vậy! mong anh thông cảm! Cool

qvluom
Sơ cấp
Sơ cấp

Tổng số bài gửi : 23
Points : 29
Join date : 26/11/2009

Re: Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS

Bài gửi  qvluom on Wed Dec 23, 2009 1:04 pm

Một câu trả lời khôn ngoan với hàm ý sâu xa. Rất tốt. Chúc bạn thành công.

thanhtan.hello
Nhập môn
Nhập môn

Tổng số bài gửi : 4
Points : 6
Join date : 06/01/2010

Re: Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS

Bài gửi  thanhtan.hello on Sun Jan 24, 2010 8:35 pm

xưa nay người học thường không sợ sai, tại vì họ luôn tìm cái đúng bạn có sai thì có người khác giúp bạn sửa sai rồi bạn sẽ đúng. bằng không bạn làm sai khi nào bạn biết sai mà bạn sửa.

ztanzzthanhz
Trung cấp
Trung cấp

Tổng số bài gửi : 60
Points : 100
Join date : 13/11/2009
Age : 26
Đến từ : Bến Tre

Re: Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS

Bài gửi  ztanzzthanhz on Mon Jan 25, 2010 12:50 am

thanhtan.hello đã viết:xưa nay người học thường không sợ sai, tại vì họ luôn tìm cái đúng bạn có sai thì có người khác giúp bạn sửa sai rồi bạn sẽ đúng. bằng không bạn làm sai khi nào bạn biết sai mà bạn sửa.

Vâng! những gì không chắc chắn em sẽ để dành cho phần hỏi đáp.

Còn ở đây, ai giải thích được thì xin giải thích dùm em, để tránh gieo rắt vào đầu của các bạn mới những suy nghĩ sai lệch như em! Neutral
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 36
Đến từ : Cần Thơ

Re: Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS

Bài gửi  admin on Tue Mar 30, 2010 8:37 pm

ztanzzthanhz đã viết:
thanhtan.hello đã viết:xưa nay người học thường không sợ sai, tại vì họ luôn tìm cái đúng bạn có sai thì có người khác giúp bạn sửa sai rồi bạn sẽ đúng. bằng không bạn làm sai khi nào bạn biết sai mà bạn sửa.

Vâng! những gì không chắc chắn em sẽ để dành cho phần hỏi đáp.

Còn ở đây, ai giải thích được thì xin giải thích dùm em, để tránh gieo rắt vào đầu của các bạn mới những suy nghĩ sai lệch như em! Neutral

Có tranh cải là điều tốt, tốt hơn nữa chúng ta tập chung giải quyết vấn đề!

Sponsored content

Re: Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS

Bài gửi  Sponsored content


    Hôm nay: Mon Nov 20, 2017 4:28 pm