Tiêu đề Thuattoan.docx ✅

Câu 1: BFS- Duyệt theo chiều sâu Trình bày: Dfs(u){ Thăm(u); vs[u] = 1; for v  ke(u) do if (vs[v] = 0) { e[v]= u; Dfs(v); Code C++: int a[100][100], n, u, vs[100], e[100]; void DfsDequy(int u) { int v; cout << u << ” ”; vs[u]= 1; for (v= 1; v<=n; v++) if (vs[v]==0 && a[u][v]==1){ e[v]= u; DfsDequy(v); Câu 2: BFS- Duyệt theo chiều rộng
Trình bày: : Bfs(u){ q = ; <Đưa u vào q>; vs[u] = 1; while q ≠  { <Lấy v ra khỏi q>; Thăm(v); for i  ke(v) do if (vs[i] = 0) { <Đưa i vào q>; vs[i] = 1; e[i] = v; Code C++: int a[100][100], n, u, vs[100], e[100], q[100]; void Bfs(int u){ int v, dq = 1, cq = 0; cq++; q[cq] = u; vs[u] = 1; while (dq <= cq){ v = q[dq]; dq++; cout << v << ” ”; for (int i= 1; i<=n; i++) if (vs[i]==0 && a[v][i]==1) { cq++; q[cq] = i; vs[i] = 1; e[i]= v; }

Trình bày: Bước 1(Kiểm tra điều kiện): Nếu G không thỏa mãn điều kiện thì kt= 0, nếu có chu trình Euler thì kt= 1; nếu có đường đi Euler thì kt= 2; Bước 2: (2.1) Nếu kt= 0  thông báo đồ thị không có chu trình/đường đi Euler và dừng; (2.2) Nếu kt= 1  chọn u là đỉnh cho trước và chuyển sang bước 3; (2.3) Nếu kt= 2  chọn u là đỉnh bậc lẻ có số hiệu nhỏ nhất và chuyển sang bước 3; Bước 3 (Xây dựng chu trình/đường đi Euler bắt đầu từ đỉnh u): (3.1) Tạo mảng CE để ghi chu trình/ đường đi Euler và Stack để xếp các đỉnh sẽ xét. Xếp đỉnh u vào Stack; (3.2) Xét đỉnh v nằm trên cùng của Stack và thực hiện: - Nếu v là đỉnh cô lập thì lấy v ra khỏi Stack và đưa vào CE. - Nếu v có đỉnh kề là x thì đưa x vào Stack sau đó xóa cạnh nối v với x; (3.3) Quay lại (3.2) cho tới khi stack rỗng; Bước 4: Xuất chu trình/đường đi Euler chứa trong CE theo thứ tự ngược lại. Code C++: