30/09/2018, 17:59

Nhờ giúp đỡ cài thuật toán duyệt đồ thị theo chiều sâu

Yêu cầu:

  • Đọc dữ liệu từ tập tin văn bản, cài thuật toán duyệt đồ thị theo chiều sâu - DFS
    (hoặc thuật toán duyệt đồ thị theo chiều rộng - BFS), xuất kết quả ra tập tin văn bản.
  • Bắt buộc cài đặt thuật toán DFS. Không bắt buộc cài đặt thuật toán BFS (cộng điểm)
    *Đề bài: Nhập ma trận kề của đồ thị từ tập tin DOTHI.txt.
  • Duyệt đồ thị bằng phép duyệt theo chiều sâu (hoặc theo chiều rộng)
    và xuất các đỉnh theo thứ tự duyệt vào tập tin _DFS.txt (_BFS.txt )
    -Ví dụ: (đồ thị trong slide bài 2, phần duyệt đồ thị)
  • Tập tin DOTHI.txt:

8
0 1 1 0 0 0 1 0
1 0 1 1 0 0 0 1
1 1 0 0 0 0 1 0
0 1 0 0 1 0 0 1
0 0 0 1 0 1 0 1
0 0 0 0 1 0 0 0
1 0 1 0 0 0 0 0
0 1 0 1 1 0 0 0

  • Tập tin _DFS.txt:

0 1 2 6 3 4 5 7

Mình code như sau nhưng chạy vẫn cứ lỗi, không biết sai chỗ nào

#include <fstream>
#include <iostream>
using namespace std;
#define max 100

void NhapMangTuFile(char TenFile[], int n, int a[][])
{
    fstream file;
    file.open(TenFile, ios_base::in);    // (1)
    if (file.is_open() == false)      // (2)
    {
        cout << "Khong mo duoc file" << endl;
        file.close();
        return;
    }
    file >> n;
    cout << " So n " << n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++){
            file << a[i][j] << " ";        // (3)
        }
    }
    file.close();          // (4)
}
void XuatMangRaFile(char TenFile[], int n, int a[][])
{
    fstream f;
    f.open(TenFile, ios_base::out);    // (1)
    if (f.is_open() == false)      // (2)
    {
        cout << "Khong tao duoc file
";
        f.close();
        return;
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++){
            f << a[i][j] << " ";        // (3)
        }
    }
    f.close();            // (4)
}
void main()
{
    int n;
    int a[max][max];
    NhapMangTuFile("input.txt", n, a);
    XuatMangRaFile("output.txt", n, a);
    system("pause");
}
Độc Cô viết 20:14 ngày 30/09/2018

Mình chạy được rồi, http://codepad.org/wp2hejIX

Minh Hoàng viết 20:12 ngày 30/09/2018

file << a[i][j] << " "; // (3)

file >>

Không có debug ở đây nên chỉ báo lỗi syntax thôi nhé sau này bạn cần thông báo lỗi cho mọi người để dễ thảo luận.
Ý tưởng hàm duyệt theo chiều sâu: xuất phát từ đỉnh bất kì, tìm kiếm các đỉnh kề của đỉnh đó, cho duyệt qua các đỉnh này (đánh dẫu đã duyệt), cứ làm như vậy.
Còn theo chiều rộng phải xây dựng một linked list để chứa các điểm cần duyệt qua.

Độc Cô viết 20:10 ngày 30/09/2018

Lỗi đây, nó báo không nhận diện được a : http://codepad.org/qGxfb7Je

Độc Cô viết 20:15 ngày 30/09/2018

Lỗi này nè bạn, ko biết sai chỗ nào http://codepad.org/qGxfb7Je

... viết 20:03 ngày 30/09/2018
void NhapMangTuFile(char TenFile[], int n, int a[][])

Bạn truyền mảng 2 chiều vào hàm cầm khai báo số dòng và số cột cho nó. Không để trống được.

Độc Cô viết 20:05 ngày 30/09/2018

Ok mình chạy được rồi, giờ mình sẽ tiếp tục viết hàm duyệt đồ thị theo chiều sâu…
Không biết có ai rành không?

Bài liên quan
0