Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Từ 1 tới 2 trên tổng số 2 kết quả

Đề tài: Thuật toán DFS từ Ma trận kề, danh sách cạnh!

  1. #1
    Ngày gia nhập
    03 2008
    Bài viết
    7

    Wink Thuật toán DFS từ Ma trận kề, danh sách cạnh!

    Xin chào các bác, em đang học về đồ thị, thầy giáo bắt em phải code lại thuật toán DFS bằng Ma trận kề, danh sách cạnh.
    Dưới đây là bài em đã làm, các bác kiểm tra lại hộ em.
    DFS - Ma trận kề:
    C Code:
    1. #include <stdio.h>
    2. #include <conio.h>
    3. #include <stdlib.h>
    4. #include <malloc.h>
    5. #define Max 50
    6. int A[50][50],n,i,j,chuaxet[50],u;
    7. FILE *fp1, *fp2;
    8. void creat_matrix(void)
    9. {
    10. printf("\n nhap so dinh cua do thi n=");
    11. scanf("%d",&n);
    12. fp1=fopen("MTke.in","w");
    13. fprintf(fp1,"%d\n",n);
    14. printf("Nhap Ma tran ke:\n");
    15. for(i=1;i<=n;i++)
    16.     {for(j=1;j<=n;j++)
    17.         {scanf("%d",&A[i][j]);
    18.          fprintf(fp1,"%3d",A[i][j]);
    19.         }
    20.       fprintf(fp1,"\n");
    21.     }
    22. fclose(fp1);
    23. }
    24. void in_matrix(void)
    25. {fp1=fopen("MTKe.in","r");
    26. if(fp1==NULL) { printf(" File khong ton tai!"); return;}
    27. printf("\n Ma tran ke vua nhap:\n");
    28. fscanf(fp1,"%3d",&n);
    29. printf("%d\n",n);
    30. for( i=1;i<=n;i++)
    31.     {for(j=1;j<=n;j++)
    32.         { fscanf(fp1,"%d",&A[i][j]);
    33.           printf("%3d",A[i][j]);
    34.         }
    35.      printf("\n");
    36.      }
    37. fclose(fp1);
    38. }
    39. void DFS(int u)
    40. {printf("%3d",u);chuaxet[u]=0;
    41. for(int i=1;i<=n;i++)
    42.     if (( A[u][i]) && (chuaxet[i]))
    43.         DFS(i);
    44. }
    45. void duyet(void)
    46. {// khoi tao mang chuaxet
    47.  for(int i=1;i<=n;i++)
    48.     chuaxet[i]=1;
    49.  DFS(u);
    50.  for(i=1;i<=n;i++)
    51.     if ( chuaxet[i]) DFS(i);
    52. }
    53. void main(void)
    54. {     clrscr();
    55.       creat_matrix();
    56.       in_matrix();
    57.       printf("Nhap dinh xuat phat duyet do thi u=");
    58.       scanf("%d",&u);
    59.       printf("\n DFS(%d):",u);
    60.       duyet();
    61. getch();
    62. }

    DFS - Danh sách cạnh:
    C Code:
    1. #include <stdio.h>
    2. #include <conio.h>
    3. #include <stdlib.h>
    4. #include <malloc.h>
    5. #define Max 50
    6. int A[50][50],n,m,i,j,k1,k2,chuaxet[50],u;
    7. FILE *fp1, *fp2;
    8. void create_DSC(void)
    9. {
    10. fp1=fopen("DSCanh.in","w");
    11. printf("\n Nhap so dinh cua do thi: n=");
    12. scanf("%d",&n);
    13. printf("\n Nhap so canh cua do thi: m=");
    14. scanf("%d",&m);
    15. fprintf(fp1,"%d  %d\n",n,m);
    16. printf("\n Liet ke danh sach canh:\n");
    17. for(i=1;i<=m;i++)
    18.     {       scanf("%d%d",&k1,&k2);
    19.         fprintf(fp1,"%d  %d\n",k1,k2);
    20.     }
    21. fclose(fp1);
    22. }
    23. void in_DS(void)
    24. { // Doc tep chua Danh sach canh
    25. fp2=fopen("DSCanh.in","r");
    26. if(fp2==NULL) { printf(" Tep khong ton tai!"); return;}
    27. int k;
    28. printf("Danh sach canh:\n");
    29. fscanf(fp2,"%d%d",&n,&m);
    30. printf("%d  %d\n",n,m);
    31.     for(i=1;i<=m;i++)
    32.         {fscanf(fp2,"%d%d",&k1,&k2);
    33.          printf("%d  %d\n",k1,k2);
    34.          }
    35. fclose(fp2);
    36. }
    37.  
    38. void DFS(int u)
    39. {printf("%3d",u);chuaxet[u]=0;
    40.  fp2=fopen("DSCanh.in","r");
    41.  fscanf(fp2,"%d%d",&n,&m);
    42.  for(i=1;i<=n;i++)
    43.     for(i=1;i<=m;i++)
    44.         {fscanf(fp2,"%d%d",&k1,&k2);
    45.         if (( k1==u)&&(chuaxet[k2]))
    46.  
    47.             DFS(k2);
    48.         else if((k2==u)&&(chuaxet[k1]))
    49.             DFS(k1);
    50.         }
    51.  fclose(fp2);
    52.  }
    53. void duyet(void)
    54. {//khoi tao mang chuaxet
    55.  for(i=1;i<=n;i++)
    56.     chuaxet[i]=1;
    57.  DFS(u);
    58.  for(i=1;i<=n;i++)
    59.     if ( chuaxet[i]) DFS(i);
    60. }
    61. void main(void)
    62. {     clrscr();
    63.       create_DSC();
    64.       in_DS();
    65.       printf("Nhap dinh xuat phat duyet do thi u=");
    66.       scanf("%d",&u);
    67.       printf("\n DFS(%d):",u);
    68.       duyet();
    69.       getch();
    70. }
    Bây giờ em phải làm BFS bằng Ma trận kề và danh sách cạnh, nhưng em làm mãi ko ra,mong các bác giúp đỡ.
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.
    I'm meo hoang!!!!!

  2. #2
    Ngày gia nhập
    03 2008
    Bài viết
    7

    ủa, ko có ai giúp bài này à, đưa lên lâu lắm rồi,chán
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.
    I'm meo hoang!!!!!

Các đề tài tương tự

  1. Bài tập C++ Sử dụng Thuật toán QuickSort sắp xếp danh sách đối tượng
    Gửi bởi nhotboy999 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 25-04-2013, 03:45 PM
  2. Lập trình C Chuyển dữ liệu từ ma trận kề thành danh sách cạnh & danh sách kề
    Gửi bởi tunglm trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 10
    Bài viết cuối: 07-12-2012, 10:15 AM
  3. Kỹ thuật C ý tưởng chuyển từ danh sách kề sang danh sách cạnh, ma trận kề
    Gửi bởi koko trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 05-08-2012, 09:29 AM
  4. Bài tập C++ Giải thuật trao đổi vị trí trong danh sách liên kết
    Gửi bởi catpth3000 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 03-01-2011, 10:59 AM
  5. Trao đổi về các giải thuật. Mọi người cùng nhau trao đổi nhé!
    Gửi bởi donvuon trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 18
    Bài viết cuối: 03-07-2010, 09:53 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn