Title Thuattoan.docx ✅

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; }
Câu 3: Tìm số TPLT bằng DFS, BFS DFS: int a[100][100], vs[100], n; int ltDfs() { int v; for (v= 1; v<= n; v++) vs[v]= 0; DfsDequy(1); for (v= 1; v<= n; v++) if (vs[v]== 0) return(0); return(1); BFS: int a[100][100], vs[100], n; int ltBfs() {int v; for (v= 1; v<= n; v++) vs[v]= 0; Bfs(1); for (v= 1; v<= n; v++) if (vs[v]== 0) return(0); return(1); Câu 4: Euler
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++: