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");
}
Bài liên quan
Mình chạy được rồi, http://codepad.org/wp2hejIX
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.
Lỗi đây, nó báo không nhận diện được a : http://codepad.org/qGxfb7Je
Lỗi này nè bạn, ko biết sai chỗ nào http://codepad.org/qGxfb7Je
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.
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?