Trang 2 trên tổng số 4 Đầu tiênĐầu tiên 1234 Cuối cùngCuối cùng
Từ 11 tới 20 trên tổng số 32 kết quả

Đề tài: Lý thuyết C++ | Giải thuật đồ thị cài đặt bằng C++

  1. #11
    Ngày gia nhập
    03 2009
    Bài viết
    28

    Mặc định Lý thuyết C++ | Giải thuật đồ thị cài đặt bằng C++

    Bạn có thể làm bài biểu diễn đồ thị bằng ma trận kề và danh sách kề không .

  2. #12
    Ngày gia nhập
    04 2008
    Bài viết
    29

    Cái BFS, em chỉ có thao tác copy past và đây là kết quả:

    Mới hôm qua chạy ok, sao giờ lại vậy nhĩ, khó hiểu quá! :(
    Bán Sim ngày sinh cho ace nào sinh ngày 9/2/889 nè, viettel nha 09.72.76.9.2.89 cần thì liên hệ 01263.599.866 nhé!

  3. #13
    Ngày gia nhập
    05 2010
    Nơi ở
    Tp HCM
    Bài viết
    9

    anh rr chạy đâu rồi?
    @itthuyloi: bfs không tìm ra đường đi ngắn nhất đâu bạn, nó chỉ dùng để tìm xem từ 1 đỉnh source nào đó có thể đi đến được những đỉnh nào khác thôi.\
    Code BFS của anh rr có bug ở việc anh sử dụng mảng trace nhằm 2 mục đích: 1 là vừa lưu vết, 2 là để đánh dấu đã được thăm hay chưa. Việc này khá nguy hiểm vì với trace[i]==0 không có nghĩa là i chưa được thăm, mà còn có nghĩa là trước i ta đã thăm đỉnh 0. Điều này gây ra vòng lặp vô hạn ở chính testcase anh đưa.
    Giải quyết: thêm vào 1 mảng visited[maxx] để đánh dấu 1 đỉnh đã được thăm hay chưa, với ý nghĩa visited[i] == 0 thì đỉnh i chưa được thăm và visited[i] == 1 tức là đỉnh i đã được thăm trước đó

    C++ Code:
    1. #include <iostream>
    2. #include <queue>
    3.  
    4. using std::cout;
    5. using std::endl;
    6. using std::endl;
    7. using std::cin;
    8.  
    9. const int maxx = 20;
    10.  
    11. void Read_input_from_user(bool grid[][maxx], int vertices)
    12. {
    13.     int u, v;
    14.     for(int x = 0; x < vertices; ++x)
    15.     {
    16.         cout << "Enter u : \t";
    17.         cin >> u;
    18.         u--;
    19.         cout << "Enter v : \t";
    20.         cin >> v;
    21.         v--;
    22.         grid[u][v] = true;
    23.                 grid[v][u] = true;
    24.         cout << "---------------------\n";
    25.     }
    26. }
    27.  
    28. void Breadth_first_search(std::queue<int> &Q, std::vector<int> &trace,
    29.                           bool grid[][maxx], int start, int nodes)
    30. {
    31.     int u;
    32.     std::vector<int> visited(maxx,0);
    33.     Q.push(start);
    34.     trace[start] = -1;
    35.     visited[start] = 1;
    36.     do{
    37.         u = Q.front();
    38.         Q.pop();
    39.         for(int v = 0; v < nodes; ++v)
    40.         {
    41.             if((grid[u][v] == true) && visited[v] == 0)
    42.             {
    43.                 Q.push(v);
    44.                 trace[v] = u;
    45.                 visited[v] = 1;
    46.             }
    47.         }
    48.     }while(!Q.empty());
    49. }
    50.  
    51. void Trace_result(std::vector<int> &trace, int start, int end, int nodes)
    52. {
    53.     cout << "From _nodes" << start + 1 << " you can visit :\n";
    54.     for(int v = 0; v < nodes; ++v)
    55.     {
    56.         if(trace[v] != 0)
    57.         {
    58.             cout << " _nodes : " << v + 1 << " , ";
    59.         }
    60.     }
    61.  
    62.     cout << "\n--------------------------------------------\n";
    63.     cout << "The path from " << start + 1 << " to " << end + 1 << '\n';
    64.    
    65.     if(trace[end] == 0){
    66.         cout << "Unavailable.! to go to from " << end + 1
    67.              << " to -> " << start + 1 << '\n';
    68.     }
    69.     else{
    70.         while(end != start)
    71.         {
    72.             cout << end + 1 << "<-";
    73.             end = trace[end];
    74.         }
    75.         cout << start + 1 << endl;
    76.     }
    77.    
    78. }
    79.  
    80.  
    81. int main()
    82. {
    83.     //Initialization
    84.     std::vector<int> trace(maxx, 0);
    85.     std::queue<int> Q;
    86.     bool grid[maxx][maxx] = {false};
    87.    
    88.     int nodes, vertices;
    89.     cout << "Please input the number of Node : \n";
    90.     cin >> nodes;
    91.     cout << "Please input the number of Vertices : \n";
    92.     cin >> vertices;
    93.  
    94.     //Set value for all vertices.
    95.     Read_input_from_user(grid, vertices);
    96.  
    97.     //Read the necessary path
    98.     int starting_position, finishing_position;
    99.     cout << "Please Input the Starting Node : \n";
    100.     cin >> starting_position;
    101.     cout << "Please Input the Finishing Node : \n";
    102.     cin >> finishing_position;
    103.     //Decrease to fit with index of C++ start from 0->size-1
    104.     starting_position--;
    105.     finishing_position--;
    106.     //Algorithm starts
    107.     Breadth_first_search(Q, trace, grid, starting_position, nodes);
    108.     Trace_result(trace, starting_position, finishing_position, nodes);
    109.    
    110.     return 0;
    111. }

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

    sao em chạy code
    C++ Code:
    1. /*Tarjan algorithm*/
    2. #include <iostream>
    3. #include <iomanip>
    4. #include <stack>
    5. #include <algorithm>
    6.  
    7. const int maxx = 20;
    8. static int strong_component = 0;
    9.  
    10. void read_input_from_user(bool grid[][maxx], int edges)
    11. {
    12.     int u, v;
    13.     for(int x = 0; x < edges; ++x)
    14.     {
    15.         std::cout << "Enter u : \t";
    16.         std::cin >> u;
    17.         u--;
    18.         std::cout << "Enter v : \t";
    19.         std::cin >> v;
    20.         v--;
    21.         grid[u][v] = true;
    22.         std::cout << "---------------------\n";
    23.     }
    24.     std::cout << std::endl << std::endl;
    25. }
    26. void Tarjan_algorithm(bool grid[][maxx], bool _freeN[], int lower[],
    27.                                           std::stack<int> &S, int number[],
    28.                                           int vertices, int count, int u)
    29. {
    30.     count++;
    31.     number[u] = count;
    32.     lower[u] = number[u];
    33.     S.push(u);
    34.     for(int v = 0; v < vertices; ++v)
    35.     {
    36.         if(_freeN[v] && grid[u][v])
    37.         {
    38.             if(number[v] != 0)
    39.             {
    40.                 lower[u] = std::min(lower[u], number[v]);
    41.             }
    42.             else
    43.             {
    44.                 Tarjan_algorithm(grid, _freeN, lower, S, number, vertices, count, v);
    45.                 lower[u] = std::min(lower[u], lower[v]);
    46.             }
    47.         }
    48.     }
    49.     if(number[u] == lower[u])
    50.     {              
    51.         strong_component++;
    52.         std::cout << "Strong Component of : " << strong_component << "\n";
    53.         int iss;
    54.         do{
    55.             iss = S.top();
    56.             S.pop();
    57.             std::cout << iss + 1 << ',';
    58.             _freeN[iss] = false;
    59.         }while(u != iss);
    60.         std::cout << "\n+++++++++++++++++++++++++\n";
    61.     }
    62. }
    63.  
    64. int main()
    65. {
    66.     int edges, vertices;
    67.     bool grid[maxx][maxx] = {};      
    68.     bool _freeN[maxx] = {};
    69.     int number[maxx] = {};
    70.     int lower[maxx] = {};
    71.     //Create an empty stack
    72.     std::stack<int> S;
    73.     for(int x = 0; x < maxx; ++x)
    74.     {
    75.         _freeN[x] = true;
    76.     }
    77.     std::cout << "Please input the number of vertices : \n";
    78.     std::cin >> vertices;
    79.     std::cout << "Please input the number of edges : \n";
    80.     std::cin >> edges;
    81.     read_input_from_user(grid, edges);
    82.        
    83.     //Initialize data
    84.     int count = 0;
    85.     for(int x = 0; x < vertices; ++x)
    86.     {
    87.         if(number[x] == 0)
    88.         {
    89.             Tarjan_algorithm(grid, _freeN, lower, S, number, vertices, count, x);
    90.         }
    91.     }
    92.     return 0;
    93. }

    bằng tubor c/c++ 5.02 mà không được?

  5. #15
    Ngày gia nhập
    03 2009
    Nơi ở
    Thái Bình
    Bài viết
    1

    Trích dẫn Nguyên bản được gửi bởi itthuyloi Xem bài viết
    Còn cái A - star sẵn post lên cho mọi người luôn đi bạn, hi`!
    Thuật toán A-star cho bài toán 8 puzzle
    Attached Files Attached Files

  6. #16
    Ngày gia nhập
    02 2011
    Bài viết
    2

    Mặc định xem giùm e đoạn code này

    em muốn duyệt qua tất cả các điểm trên đồ thị và đưa ra 1 danh sách. nhưng sao chạy thì bị breakpoint

    C++ Code:
    1. #include <iostream>
    2. #include <queue>
    3. using namespace std;
    4. const int maxx=20;
    5. void input(bool mt[maxx][maxx],int ver)
    6. {
    7.     int u,v;
    8.     cout<<"nhap ma tran ke: \n";
    9.     for (int i=0;i<ver;i++)
    10.     {
    11.         cout<<"nhap u:   \n";
    12.         cin>>u;
    13.         cout<<"nhap v:   \n";
    14.         cin>>v;
    15.         cout<<"-------------------\n";
    16.         mt[u][v]=true;
    17.         mt[v][u]=true;
    18.  
    19.     }
    20. }
    21. void bfs(bool mt[maxx][maxx],std::vector<int> &trace,bool visited[maxx],
    22.         std::queue<int> &q,int u,int nodes)
    23. {
    24.     int i;
    25.     q.push(u);
    26.     visited[u]=true;
    27.     do{
    28.         u=q.front();
    29.         q.pop();
    30.         for (i=0;i<nodes;i++)
    31.             if(mt[u][i]==true && visited[i]==false)
    32.             {
    33.                 visited[i]=true;
    34.                 q.push(i);
    35.                 trace[u]=i;
    36.             }
    37.         trace[i]=0;
    38.     }while(q.empty());
    39. }
    40. void result_trace(std::vector<int> &trace,int u)
    41. {
    42.     cout<<"thu tu duyet la: \n";
    43.     while(trace[u]!=0)
    44.     {
    45.         cout<<u<<"->";
    46.         u=trace[u];
    47.     }
    48. }
    49. int main()
    50. {
    51.     std::vector<int> trace;
    52.     std::queue<int> q;
    53.     bool visited[maxx]={false};
    54.     bool mt[maxx][maxx]={false};
    55.     int u,nodes,ver;
    56.     cout<<"\nnhap so diem: ";
    57.     cin>>nodes;
    58.     cout<<"\nnhap so canh: ";
    59.     cin>>ver;
    60.     input(mt,ver);
    61.     cout<<"\nnhap diem bat dau: \n";
    62.     cin>>u;
    63.     bfs(mt,trace,visited,q,u,nodes);
    64.     result_trace(trace,u);
    65.     return 0;
    66. }
    Đã được chỉnh sửa lần cuối bởi icehawk : 15-03-2011 lúc 11:07 AM.

  7. #17
    Ngày gia nhập
    01 2010
    Bài viết
    18

    Sorry vì đã moi topic này lên, mình muốn hỏi là nếu áp dụng với đồ thị có hướng thì cần làm thế nào? đồ thị có hướng mình đã biểu diễn qua ma trận kề

  8. #18
    Ngày gia nhập
    05 2011
    Bài viết
    1

    thanks you so much

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

    các pro ơi giải thích cho em hiểu trong cái hàm Read_input_from_user(...) có cái đoạn u--, rồi v-- là sao?? sao lại giảm nó đi làm gì.

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

    @bong2432: vì khi chúng ta nhập sẽ qui ước đỉnh 1->n, nhưng mãng trong C/C++ chỉ hiểu từ 0->n-1.

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

  1. Các giải thuật sắp xếp - Lý thuyết và cài đặt trên C
    Gửi bởi PoPoPoPo trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 29
    Bài viết cuối: 28-05-2019, 11:45 AM
  2. Các giải thuật tìm kiếm - Lý thuyết và cài đặt trên C
    Gửi bởi PoPoPoPo trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 5
    Bài viết cuối: 24-02-2015, 05:21 PM
  3. Lý thuyết đồ thị | Giải thuật DFS (Depth First Search)
    Gửi bởi vie_kainznz trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 1
    Bài viết cuối: 14-01-2013, 10:48 PM
  4. [Lý thuyết giải thuật] Một số bài tập về giải thuật và cách giải
    Gửi bởi hailoc12 trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 6
    Bài viết cuối: 27-01-2010, 04:10 PM
  5. Lý thuết đồ thị | Bài tập Lý thuyết đồ thị
    Gửi bởi soda_chanhmuoi 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: 11-02-2008, 08:01 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