Hỏi về thuật toán DFS và BFS

[Nam_Nguyen9 (Nam Nguyễn)]

mọi người cho em hỏi code về thuật toán dfs và bfs đc k ạ từ bước thứ 2 em chưa hiểu. em đã cài đặt sẵn struct stack và queue r ạ

Cho ma trận kề của đồ thị. Viết hàm duyệt đồ thị theo chiều sâu (DFS) với đỉnh xuất phát v và xuất ra màn hình thứ tự các đỉnh duyệt được.

Hướng dẫn:

• Bước 1: khởi tạo 1 mảng VISIT, 1 stack rỗng, thêm S vào stack, đánh dấu S đã viếng thăm.
• Bước 2: (bước lặp) Trong khi stack khác rỗng:
  • Lấy u ra khỏi stack
  • Nếu u có đỉnh kể chưa thăm
    • Chỉ chọn 1 đỉnh v kề u chưa thăm.
    • Đánh dấu thăm v
    • Đẩy u vào lại stack (lưu lại bước lùi)
    • Đẩy v vào stack
• Bước 3: truy vết đường đi nếu cần

[rogp10]

Vui lòng đọc lại bước 1

S ở đây là đỉnh xuất phát

[Nam_Nguyen9 (Nam Nguyễn)]

ý em hỏi là từ bước 2 code như nào ạ em làm đến đây là k nghĩ ra được b2 á bác !

void DFS(DOTHI g, VERTEX s, VERTEX u, int chuaxet[MAX])
{
    TYPESTACK st;
    InitStack(st);
    PushStack(s, st);
    for (int i = 0; i < g.n; i++)
    {
        chuaxet[i] = 0;
        chuaxet[s] = 1;
    }
    // other stuff
}

[rogp10]

Cái này tùy vào cấu trúc của DOTHI và VERTEX nếu bạn là người cài đặt nó, nếu không thì chắc cũng có interface rồi. Sử dụng danh sách kề là hay hơn cả.