Chuyên đề Tin 12 CTST Bài 3.4. Duyệt đồ thị theo chiều sâu

Cho đồ thị G1 như ở Hình 1. Hãy tìm đường đi ngắn nhất từ đỉnh H đến đỉnh D bằng thuật toán duyệt đồ thị theo chiều rộng.

Em hãy minh hoạ duyệt theo chiều sâu của đồ thị G2 ở Hình 2 (tương tự như Bảng 1) và bắt đầu từ đỉnh 2.

Dùng thuật toán duyệt đồ thị theo chiều sâu xuất phát từ đỉnh 1. Hãy cho biết thứ tự duyệt các đỉnh của đồ thị ở Hình 4.

Cho đồ thị G5 (Hình 5). Chỉ ra đường đi từ đỉnh F đến đỉnh J bằng thuật toán duyệt đồ thị theo chiều sâu trong đồ thị G5.

Nhiệm vu: Duyệt đồ thị theo chiều sâu

Yêu cầu: Chương trình sau được viết bằng Phython duyệt đồ thị theo chiều sâu, với đồ thị Graph được biểu diễn bằng danh sách kề.

Một đồ thị được gọi là liên thông nếu tồn tại ít nhất một đường đi giữa hai đỉnh bất kì của nó. Chẳng hạn, đồ thị ở Hình 6a là liên thông còn đô thị ở Hình 6b là không liên thông (không có đường đi từ đỉnh 0 tới đỉnh 3).

Yêu cầu: Áp dụng thuật toán duyệt đồ thị theo chiều sâu. Thực hiện xây dựng thuật toán kiểm tra xem đồ thị G = (V, E) cho trước có liên thông hay không.