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

Đề tài: Giải thuật DFS và BFS trên C++

  1. #1
    Ngày gia nhập
    04 2009
    Nơi ở
    một căn hộ nhỏ trên trái đất
    Bài viết
    372

    Mặc định Giải thuật DFS và BFS trên C++

    Khi đọc bài viết ở Tìm đường đi ngắn nhất có giao diện đồ họa mình đã muốn tải ngay về để thử nghiệm vì nó liên quan đến lý thuyết đồ thị, tiếc rằng file đó không chạy được trên máy mình.
    Mình đang học phần lý thuyết đồ thị của toán rời rạc, khi học qua giải thuật DFS(tìm kiếm theo chiều sâu) và BFS(tìm kiếm theo chiều rộng) thầy giáo có yêu cầu làm bài tập áp dụng hai giải thuật này bằng pascal, nhưng mình không biết pascal nên dùng C++. Tại thời điểm mình viết bài này, thì vẫn chưa hết hạn, nhưng mình chia sẻ với mọi người vì lớp mình rất ít đứa biết về C++,thậm chí ngay đến giải thuật nhiều đứa còn không hiểu. Mình đã thử nghiệm và thấy chạy ổn. Nhưng vẫn cần mọi người đóng góp thêm
    Địa chỉ tải tại đây: http://www.mediafire.com/download/goz31gqyzmm/graphtheory.rar
    Trong đó bao gồm cả file chạy và mã nguồn.
    Chương trình này yêu cầu nhập vào danh sách cạnh dưới dạng đỉnh đầu và cuối và sau đó khi bạn yêu câu tìm đường đi từ đỉnh x đến đỉnh y chương trình sẽ tìm đường đi đó nếu tìm được sẽ hiện kết quả.
    Những ai đã và đang học toán rời rạc sẽ không có vấn đề gì khi thử nghiệm chương trình. Còn ai chưa học nó thì chắc khó mà biết phải làm gì để kiểm tra tính đúng đắn của chương trình.
    Đã được chỉnh sửa lần cuối bởi icttrack : 20-04-2009 lúc 09:29 AM.

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

    Bài của bạn viết chưa rõ ràng lắm.
    Ví dụ như ở đoạn nhập dữ liệu, bạn phải nói rõ là nhập danh sách kề chứ?
    Thứ 2, để người dùng hình dung rõ ràng sự khác nhau giữa 2 thuật toán DFS và BFS thì ngay trong phần liên thông bạn hãy dùng 2 thuật toán đó đi. Phần kiểm tra liên thông bạn hãy viết từng bước như xuất phát từ đâu, đi tới đâu, .... là ok

  3. #3
    Ngày gia nhập
    04 2009
    Nơi ở
    một căn hộ nhỏ trên trái đất
    Bài viết
    372

    Trích dẫn Nguyên bản được gửi bởi metal_shield Xem bài viết
    Bài của bạn viết chưa rõ ràng lắm.
    Ví dụ như ở đoạn nhập dữ liệu, bạn phải nói rõ là nhập danh sách kề chứ?
    Thứ 2, để người dùng hình dung rõ ràng sự khác nhau giữa 2 thuật toán DFS và BFS thì ngay trong phần liên thông bạn hãy dùng 2 thuật toán đó đi. Phần kiểm tra liên thông bạn hãy viết từng bước như xuất phát từ đâu, đi tới đâu, .... là ok
    Quá trình xử lý thì mình dùng danh sách kề, nhưng khi người dùng nhập vào thì là danh sách cạnh. Với cả sau khi bạn nhập danh sách cạnh xong rồi, chương trình cho phép bạn đổi thuật toán để tiện so sánh giữa hai thuật toán. Mình nghĩ nếu bạn chạy chương trình thì phải thấy chứ

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

    Wink bạn có thể post code của bài toán DFS lên forum được không

    mình đang học toán rời rạc.cũng gặp bài tập này.khó wa' hichic,bạn post cost lên forum giúp mình na.tks

  5. #5
    Ngày gia nhập
    04 2009
    Nơi ở
    một căn hộ nhỏ trên trái đất
    Bài viết
    372

    Trích dẫn Nguyên bản được gửi bởi mr_kent0602 Xem bài viết
    mình đang học toán rời rạc.cũng gặp bài tập này.khó wa' hichic,bạn post cost lên forum giúp mình na.tks
    Bạn không đọc kĩ ở trên rồi, trong file chạy đã có bao gồm cả mã nguồn. Bạn có thể tải về được với địa chỉ mình cung cấp ở trên.

    Không biết ở đây có ai học lý thuyết đồ thị trước khi học Cấu trúc dữ liệu và giải thuật không?.
    Sao ở trường mình cái gì cũng học ngược thế nhỉ?

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

    Mặc định Giải thuật DFS và BFS trên C++

    - Dù C hay C++ thì cũng không nên dùng goto.
    - Code dùng new mà chẳng thấy delete đâu cả.
    - Thiếu const và handle exception.
    - Đoạn này :
    C++ Code:
    1. template<typename T>
    2.  
    3. T LinkedList< T >::retrieveItem() {
    4.  
    5.     if(ptri==NULL)
    6.  
    7.         return -1;
    8.  
    9.     Item <T> *curPtr=ptri;
    10.  
    11.     ptri=ptri->nextPtr;
    12.  
    13.     return curPtr->data;
    14.  
    15. }
    Code dùng template là một typename T, giả sử kiểu dữ liệu là char* or class type, vậy trả về trừ -1 mang ý nghĩa gì nhỉ ?
    - DFS và BFS chẳng có liên quan gì tới Item cả, tại sao cho nó là friend ? sau này chẳng lẽ nếu dùng giải thuật khác thì cứ mỗi lần mỗi modify Item à.

  7. #7
    Ngày gia nhập
    04 2009
    Nơi ở
    một căn hộ nhỏ trên trái đất
    Bài viết
    372

    Anh góp ý rất thẳng thắn, em rất thích như vậy.
    -Về vấn đề cấp phát động, thật sự là em đã sơ xuất, quên không dùng delete. Lẽ ra em phải làm nó khi ở destructor và ở main()
    -Tại thời điểm viết chương trình, em chưa học handle exception của C/C++.
    -Lệnh goto em biết được khuyến cáo không dùng nhưng em thấy nó tiện lợi cho chương trình của mình.

    C++ Code:
    1. template<typename T>
    2.  
    3. T LinkedList< T >::retrieveItem() {
    4.  
    5.     if(ptri==NULL)
    6.  
    7.         return -1;
    8.  
    9.     Item <T> *curPtr=ptri;
    10.  
    11.     ptri=ptri->nextPtr;
    12.  
    13.     return curPtr->data;
    14.  
    15. }
    Đoạn mã này thực ra đúng là em thấy không ổn nên chỉ dùng nó để thử nghiệm. Nếu anh để ý trong mã thực thi chính nằm ở file graph.cpp thì em đã comment cái vùng mã có sử dụng phương thức retrieveItem nên nó không được dùng biên dịch chương trình. Một lần nữa lại là do em quên không xóa phương thức này đi khỏi LinkedList.
    Vì lẽ đó, em không có phương thức nào để truy xuất toàn bộ đối tượng có trong LinkedList (tức là các item) do đó với DFS và BFS em phải khai báo nó là friend với Item để có thể duyệt thủ công qua tất cả phần tử có trong LinkedList. Nếu em không khai báo friend thì trong hai khai báo ở trong thân hai hàm trên
    Với DFS
    C++ Code:
    1. Item < T> *curPtr=v[s].firstItem;
    Với BFS
    C++ Code:
    1. Item < T> *curPtr;

    sẽ không thể làm được.

    Cảm ơn vì sự góp ý của anh.
    Đã được chỉnh sửa lần cuối bởi icttrack : 08-05-2009 lúc 03:47 PM.

  8. #8
    Ngày gia nhập
    09 2013
    Bài viết
    3

    ai có lí thuyết báo cáo liên quan đến DFS thì cho mình xin cận ngày báo cáo rồi mà làm lý thuyết không kịp các bác ạ, giúp giùm e e cảm ơn các bác nhiều lắm........

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: 28
    Bài viết cuối: 15-05-2013, 11:10 AM
  2. Giải thuật tìm tất cả đường đi trên 1 đồ thị?
    Gửi bởi ndp1007 trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 2
    Bài viết cuối: 24-04-2011, 10:22 PM
  3. Bài tập C++ Giải thuật đệ quy-Tìm max min trên C?
    Gửi bởi sky_night 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: 27-09-2010, 11:12 PM
  4. Giải thuật đệ qui trên C++ cho hàm Acker
    Gửi bởi trang801 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 07-08-2010, 03:25 PM
  5. Giải thuật Xử Lý phân thức trên C++
    Gửi bởi love_games trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 07-05-2009, 08:56 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