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

Đề tài: Thuật toán BFS viết bằng C++, code không chạy được?

  1. #1
    Ngày gia nhập
    11 2007
    Bài viết
    3

    Mặc định Thuật toán BFS viết bằng C++, code không chạy được?

    Ai giúp em viết code Thuật toán tìm kiếm BFS với. Em viết rồi nhưng ko chạy được.

    C++ Code:
    1. #include <iostream>
    2. #include <iomanip>
    3. #include <fstream>
    4. #include <queue>
    5.  
    6. using namespace std;
    7.  
    8. typedef queue<int> Queue;
    9.  
    10. ///////////////////////////////////////////////////////////
    11. // nhap graph tu file du lieu
    12. void InitGraph(int ** &A, int* & Trace,int &n, int &m, int& src, int& dest, char* file_name)
    13. {
    14.     int u,v;
    15.  
    16.     ifstream    fin(file_name);
    17.     if(!fin)
    18.     {
    19.         cout << "Khong mo duoc file du lieu!" << endl;
    20.         return;
    21.     }
    22.     else
    23.     {
    24.         // doc gia tri  : n dinh va m canh tu file du lieu
    25.         //              : src la dinh nguon, dest la dich
    26.         fin >> n >> m >> src >> dest;
    27.  
    28.         // cap phat bo nho cho cac dinh trung gian di qua
    29.         Trace   =   new int[n];
    30.         for(int i = 0; i < n; i++)
    31.             Trace[i]    =   -1;
    32.  
    33.         Trace[src] = -2;
    34.  
    35.         // cap phat bo nho cho ma tran ke
    36.         A   =   new (int*[n]);
    37.         for(int i = 0; i < n; i++)
    38.             A[i]    =   new int[n];
    39.  
    40.         // khoi tao ma tran ke cac dinh bang 0
    41.         for(int i = 0; i < n; i++)
    42.             for(int j = 0; j < n; j++)
    43.                 A[i][j] =   0;
    44.  
    45.         // doc va gan gia tri cho cac canh trong graph
    46.         for(int i = 0; i < m; i++)
    47.         {
    48.             fin >> u >> v;
    49.             A[u][v] =   1;
    50.             A[v][u] =   1;
    51.         }
    52.     }
    53.     fin.close();
    54. }
    55. /////////////////////////////////////////////////////////////
    56. // thuat toan khong de quy Breadth First Search duyet graph bat dau tu 1 dinh src
    57. // phien ban nay dung lop QUEUE co san trong thu vien STL
    58. void BFS(int **A, int *& Trace, int n, int src)
    59. {
    60.     Queue   Q;
    61.     int u,v;
    62.  
    63.     Q.push(src);
    64.     do
    65.     {
    66.         u   =   Q.front();
    67.         Q.pop();
    68.  
    69.         for(v = 0; v < n; v++)
    70.         {
    71.             if(A[u][v] && Trace[v] == -1)
    72.             {
    73.                 Q.push(v);
    74.                 Trace[v]    =   u;
    75.             }
    76.         }
    77.     }
    78.     while (!Q.empty());
    79. }
    80. /////////////////////////////////////////////////////////////
    81. // thuat toan khong de quy Breadth First Search duyet graph bat dau tu 1 dinh src
    82. // phien ban nay khong dung lop QUEUE co san trong thu vien STL
    83. void BFS2(int **A, int *& Trace, int n, int src)
    84. {
    85.     int *que    =   new int[n];
    86.     int W, R; // W : chi so se ghi them; R : chi so de doc tu que
    87.     int u,v;
    88.  
    89.     W = R = -1;
    90.  
    91.     W   =   W+1;
    92.     que[W%n]    =   src;
    93.     do
    94.     {
    95.         R   =   (R+1);
    96.         u   =   que[R%n];
    97.        
    98.         for(v = 0; v < n; v++)
    99.         {
    100.             if(A[u][v] && Trace[v] == -1)
    101.             {
    102.                 W   =   W+1;
    103.                 que[W%n]    =   v;
    104.                 Trace[v]    =   u;
    105.             }
    106.         }
    107.     }
    108.     while (R < W);
    109. }
    110. /////////////////////////////////////////////////////////////
    111. // xac dinh duong di tu src den dest
    112. void PrintPath(int **A, int *Trace, int n, int src, int dest)
    113. {
    114.     if(Trace[dest] == -1)
    115.         cout << "Khong co duong di tu " << src << " den " << dest << endl;
    116.     else
    117.     {
    118.         cout << "Duong di tu " << src << " den " << dest << " : " << endl;
    119.         while(dest != src)
    120.         {
    121.             cout << dest << " <-- ";
    122.             dest    =   Trace[dest];
    123.         }
    124.         cout << src << endl;
    125.     }
    126. }
    127. /////////////////////////////////////////////////////////////////
    128. void main()
    129. {
    130.     int **A, *Trace, m,n,src,dest;
    131.  
    132.     InitGraph(A,Trace,n,m,src,dest,"Data.in");
    133.     BFS2(A,Trace,n,src);
    134.     PrintPath(A,Trace,n,src,dest);
    135. }

  2. #2
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Tớ sẽ gởi lên cho cậu sau. Vấn đề là cậu phải nắm bắt được ý tưởng chính của nó để tự viết cho riêng mình. Ok

  3. #3
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917


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

  1. Xin code thuật toán dijkstra viết bằng C#
    Gửi bởi duonggadget trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 1
    Bài viết cuối: 07-03-2012, 08:22 PM
  2. Bài tập C++ Em viết code này nhưng những lỗi báo em sửa oy thì vẫn không chạy được
    Gửi bởi minhthanh_vfu trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 07-11-2011, 10:46 PM
  3. Code bài toán n Hậu viết bằng C++. Chương trình không chạy nếu n > 14?
    Gửi bởi we004338 trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 1
    Bài viết cuối: 19-09-2011, 10:52 PM
  4. code tìm cây có trọng lượng nhỏ nhất bằng giải thuật prim-cách chạy tay code này
    Gửi bởi ruacon_206 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: 25-04-2011, 02:27 PM
  5. Code kiểm 3 đỉnh thuộc tam giác viết bằng C. Kiểm tra giúp mình thuật toán với?
    Gửi bởi luannguyenit trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 5
    Bài viết cuối: 23-08-2010, 01:32 AM

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