Từ 1 tới 9 trên tổng số 9 kết quả

Đề tài: thuật toán tìm kiếm theo chiều sâu trong môn TRR. Cần giúp đỡ?

  1. #1
    Ngày gia nhập
    01 2010
    Bài viết
    4

    Mặc định thuật toán tìm kiếm theo chiều sâu trong môn TRR. Cần giúp đỡ?

    Mình đang học đến các giải thuật tìm kiếm trên đồ thị. Có bài về tìm kiếm theo chiều sâu cần các pác giúp đỡ.Để KTra việc duyệt mỗi đỉnh đúng 1 lần, mình sdungj 1 mảng chuaxet[] gồm n ptu tương ứng với n đỉnh.Nếu đỉnh thứ i đã đc duyệt, ptu tương ứng trong mảng chuaxet[] có gtri FALSE, ngược lại là TRUE.
    Thủ tục DFS() sẽ thăm tất cả các đỉnh cùng thành phần liên thông với mỗi đỉnh đúng 1 lần. Để đăm duyệt tất cả các đỉnh của đồ thị ( có thể có nhìu thành phần liên thông):
    for(int i=1; i<=n; i++)
    chuaxet[i]=TRUE; /* Thiết lập gtri bân đầu cho mảng chuaxet[] */
    for(i=1; i<=n;i++)
    if(chuaxet[i])
    DFS(i);

    Đây là code của mình nhưng khi chạy thì chỉ có nhập đc có ma trận kề, kết quả duyệt thì ko ra.Hic!




    #include <stdio.h>
    #include <conio.h>
    #include <stdlib.h>
    #define MAX 100
    #define TRUE 1
    #define FALSE 0
    void Init(int G[][MAX], int n){
    int i, j;
    printf("\n So dinh do thi:");
    scanf("%d",&n);
    printf("\n Ma tran ke cua do thi:");
    for(i=1; i<=n;i++){
    printf("\n");
    for(j=1; j<=n;j++){
    printf("\n G[%d][%d]=",i,j);
    scanf("%d", &G[i][j]);
    }
    }
    }
    int DFS(int G[][MAX], int n, int v, int chuaxet[]){
    int u;
    for(v=1;v<=n;v++)
    printf("%3d",v);chuaxet[v]=FALSE;
    for(u=1; u<=n; u++){
    if(G[v][u]==1 && chuaxet[u])
    DFS(G,n, u, chuaxet);
    return u;
    }
    }
    int main(void){
    int G[MAX][MAX], n, chuaxet[MAX],i;
    Init(G,n);
    for(int i=1; i<=n; i++)
    chuaxet[i]=TRUE;
    printf("\n\n");
    for(i=1; i<=n;i++)
    if(chuaxet[i])
    DFS( G,n, i, chuaxet);
    getch();
    }

  2. #2
    Ngày gia nhập
    04 2009
    Bài viết
    35

    Code:
    int DFS(int G[][MAX], int n, int v, int chuaxet[]){ 
    int u; 
    for(v=1;v<=n;v++)
    printf("%3d",v);chuaxet[v]=FALSE; 
    for(u=1; u<=n; u++){ 
    if(G[v][u]==1 && chuaxet[u]) 
    DFS(G,n, u, chuaxet); 
    return u;
    }
    điều kiện if(G[v][u]==1 && chuaxet[u]) phải là if(G[v][u]==1 && !chuaxet[u])

  3. #3
    Ngày gia nhập
    01 2010
    Bài viết
    4

    chuaxet[u] là đúng rồi mà bạn. Vì ở đây đang xét điều kiện để in ra đỉng u là kề của v, vậy v phải chưa đc xét tức chuaxet[v]=TRUE

  4. #4
    Ngày gia nhập
    04 2009
    Bài viết
    35

    int DFS(int G[][MAX], int n, int v, int chuaxet[]){
    int u;
    for(v=1;v<=n;v++)
    printf("%3d",v);chuaxet[v]=FALSE;
    for(u=1; u<=n; u++){
    if(G[v][u]==1 && chuaxet[u])
    DFS(G,n, u, chuaxet);
    return u;
    }
    không thể gọi để quy chính DFS được !
    phải có thếm một hàm DFS1 nữa và hàm này đệ quy !
    DFS(void) có nhiệm vụ khởi tạo, đưa các biến chưa xét về false và xét điều kiện để gọi DFS1 lần đầu dk là if(G[v][u]==1 && !chuaxet[u]) ( ơ đây chuaxet[u] là false thì mới chạy như để dk là đúng thì cần đảo lại là !chuaxet[u] )
    DFS1(G[][MAX], int n, v, chuaxet[]) thì để đánh đấu đã duyệt vào chưa xét !
    bạn tự code lại nha mình bùn ngủ quá !:P

  5. #5
    Ngày gia nhập
    09 2009
    Bài viết
    240

    Trích dẫn Nguyên bản được gửi bởi acuvodoi Xem bài viết
    Mình đang học đến các giải thuật tìm kiếm trên đồ thị. Có bài về tìm kiếm theo chiều sâu cần các pác giúp đỡ.Để KTra việc duyệt mỗi đỉnh đúng 1 lần, mình sdungj 1 mảng chuaxet[] gồm n ptu tương ứng với n đỉnh.Nếu đỉnh thứ i đã đc duyệt, ptu tương ứng trong mảng chuaxet[] có gtri FALSE, ngược lại là TRUE.
    Thủ tục DFS() sẽ thăm tất cả các đỉnh cùng thành phần liên thông với mỗi đỉnh đúng 1 lần. Để đăm duyệt tất cả các đỉnh của đồ thị ( có thể có nhìu thành phần liên thông):
    for(int i=1; i<=n; i++)
    chuaxet[i]=TRUE; /* Thiết lập gtri bân đầu cho mảng chuaxet[] */
    for(i=1; i<=n;i++)
    if(chuaxet[i])
    DFS(i);

    Đây là code của mình nhưng khi chạy thì chỉ có nhập đc có ma trận kề, kết quả duyệt thì ko ra.Hic!
    Tham khảo ở đây nè, duyệt tất cả các thành phần liên thông.
    C++ Code:
    1. #include <stdio.h>
    2. #define max 10
    3.  
    4. struct vector
    5. {
    6.     int v[max];
    7.     int size;
    8.     int &operator [] (int k) {return v[k];}
    9. };
    10.  
    11. class graph
    12. {
    13.     vector v[max];
    14.     int visit[max];
    15.     int size;
    16.     int count;
    17.     public:
    18.         graph(int _size = max);
    19.         vector &operator [] (int k) {return v[k];}
    20.         void input(int &);
    21.         void dfs(int);
    22.         void run(int &);
    23. };
    24.  
    25. graph::graph(int _size)
    26. {
    27.     size = _size; count = 0;
    28.     for (int k = 0; k < size; k++)
    29.         {
    30.             visit[k] = 0;
    31.             for (int j = 0;j < size; j++) v[k][j] = 0;
    32.         }
    33. }
    34.  
    35. void graph::input(int &start)
    36. {
    37.     printf("\nSo dinh: "); scanf("%d",&size);
    38.     printf("\n Nhap 1 neu hai dinh duoc noi truc tiep voi nhau\n");
    39.     for (int k = 0; k < size-1; k++)
    40.         for (int j = k+1; j < size; j++)
    41.             {
    42.                 printf("Dinh %d va dinh %d: ",k,j); scanf("%d",&v[k][j]);
    43.                 v[j][k] = v[k][j];
    44.             }
    45.     printf("\nDinh xuat phat:");scanf("%d", &start);
    46. }
    47.  
    48. void graph::dfs(int start)
    49. {
    50.     if(visit[start]==0)
    51.         {
    52.             visit[start] = 1;
    53.             count ++;
    54.             printf("%d\t",start);
    55.             for (int k = 0; k < size; k++) if (v[start][k]) dfs(k);
    56.         }
    57. }
    58.  
    59. void graph::run(int & start)
    60. {
    61.     input(start);
    62.     while (count < size)
    63.         {
    64.             if(visit[start] == 0) printf("\nThanh phan lien thong:\n");
    65.             dfs(start);
    66.             ++start %= size;
    67.         }
    68. }
    69.  
    70. void main()
    71. {
    72.     graph g;
    73.     int start;
    74.     g.run(start);
    75. }

  6. #6
    Ngày gia nhập
    01 2010
    Bài viết
    4

    Mặc định thuật toán tìm kiếm theo chiều sâu trong môn TRR. Cần giúp đỡ?

    Trích dẫn Nguyên bản được gửi bởi supnobita Xem bài viết
    không thể gọi để quy chính DFS được !
    phải có thếm một hàm DFS1 nữa và hàm này đệ quy !
    DFS(void) có nhiệm vụ khởi tạo, đưa các biến chưa xét về false và xét điều kiện để gọi DFS1 lần đầu dk là if(G[v][u]==1 && !chuaxet[u]) ( ơ đây chuaxet[u] là false thì mới chạy như để dk là đúng thì cần đảo lại là !chuaxet[u] )
    DFS1(G[][MAX], int n, v, chuaxet[]) thì để đánh đấu đã duyệt vào chưa xét !
    bạn tự code lại nha mình bùn ngủ quá !:P
    Ban viết luôn ra hộ mình đc ko? Thuật toán của bạn bên dưới mình ko hỉu :|

  7. #7
    Ngày gia nhập
    04 2009
    Bài viết
    35

    Code:
    #include<stdio.h>
    #include<conio.h>
    void DFS(int a[][100],int n,int tham[],int m,FILE *f)
    {
    
       tham[m]=1;
       fprintf(f,"\t%d",m);
       for(int i=1;i<=n;i++)
          if(a[i][m]==1&&tham[i]==0)
    	 DFS(a,n,tham,i,f);
    }
    void main()
    {
       clrscr();
       int n,a[100][100],tham[100];
       FILE *f;
       int i,j;
    
       if((f=fopen("C:\\dothi.txt","rt"))==NULL)
          printf("\nKo the mo duoc file");
       else
       {
          fscanf(f,"%d",&n);
          for(i=1;i<=n;i++)
    	 for(j=1;j<=n;j++)
    	    a[i][j]=0;
          while((fscanf(f,"%d%d",&i,&j))!=EOF)
    	 a[i][j]=a[j][i]=1;
       }
       fclose(f);
       FILE *t;
       t=fopen("C:\\matranke.txt","wt");
    
       for(i=1;i<=n;i++)
       {
          for(j=1;j<=n;j++)
    	 fprintf(t,"\t%d",a[i][j]);
          fprintf(t,"\n\n");
       }
       fprintf(f,"\n");
       for(i=1;i<=n;i++)
          tham[i]=0;
       for(i=1;i<=1;i++)
       DFS(a,n,tham,i,t);
       fclose(t);
       getch();
    
    }

  8. #8
    Ngày gia nhập
    01 2010
    Bài viết
    4

    Trích dẫn Nguyên bản được gửi bởi supnobita Xem bài viết
    Code:
    #include<stdio.h>
    #include<conio.h>
    void DFS(int a[][100],int n,int tham[],int m,FILE *f)
    {
    
       tham[m]=1;
       fprintf(f,"\t%d",m);
       for(int i=1;i<=n;i++)
          if(a[i][m]==1&&tham[i]==0)
    	 DFS(a,n,tham,i,f);
    }
    void main()
    {
       clrscr();
       int n,a[100][100],tham[100];
       FILE *f;
       int i,j;
    
       if((f=fopen("C:\\dothi.txt","rt"))==NULL)
          printf("\nKo the mo duoc file");
       else
       {
          fscanf(f,"%d",&n);
          for(i=1;i<=n;i++)
    	 for(j=1;j<=n;j++)
    	    a[i][j]=0;
          while((fscanf(f,"%d%d",&i,&j))!=EOF)
    	 a[i][j]=a[j][i]=1;
       }
       fclose(f);
       FILE *t;
       t=fopen("C:\\matranke.txt","wt");
    
       for(i=1;i<=n;i++)
       {
          for(j=1;j<=n;j++)
    	 fprintf(t,"\t%d",a[i][j]);
          fprintf(t,"\n\n");
       }
       fprintf(f,"\n");
       for(i=1;i<=n;i++)
          tham[i]=0;
       for(i=1;i<=1;i++)
       DFS(a,n,tham,i,t);
       fclose(t);
       getch();
    
    }
    Khi chạy nó báo lỗi ko mở đc file là sao hả bạn?

  9. #9
    Ngày gia nhập
    11 2011
    Bài viết
    11

    Mặc định Dfs

    sao không ai viết bằng ngôn ngữ C hộ cái toàn prinf với scan gì do hix

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

  1. Lập trình C Cần minh họa cho thuật toán tìm kiếm theo chiều sâu (depth first search)
    Gửi bởi nguoimoihoc 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: 12-10-2013, 09:41 AM
  2. Kỹ thuật C++ Thuật toán tìm kiếm theo chiều sâu này có dạng như thế nào?
    Gửi bởi quan100157 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 14-03-2013, 10:48 AM
  3. Trả lời: 4
    Bài viết cuối: 10-09-2012, 06:34 PM
  4. Bài tập C Tìm kiếm theo chiều sâu DFS
    Gửi bởi pnst_1811 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 01-04-2012, 07:19 PM
  5. Thuật toán tìm kiếm theo chiều rộng. Giúp mình?
    Gửi bởi k9zzz trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 3
    Bài viết cuối: 28-08-2010, 05:11 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