Giải Chuyên đề Tin học 12 Chân trời sáng tạo bài 3: Duyệt đồ thị theo chiều rộng
Bài 3: Duyệt đồ thị theo chiều rộng
Giải Chuyên đề Tin học 12 bài 3: Duyệt đồ thị theo chiều rộng là tài liệu hữu ích giúp bạn đọc có thể trau dồi nội dung kiến thức, học tập tốt hơn môn Tin học 12 Chân trời sáng tạo. Mời các bạn cùng theo dõi bài viết dưới đây.
Khởi động trang 59 Chuyên đề Tin 12 Chân trời
Bản đồ giao thông kết nối 8 địa điểm nổi tiếng được mô tả như đồ thị G, (Hình 1). Theo em, có tồn tại một hành trình đi từ địa điểm D đến địa điểm G sao cho phải đi qua ít địa điểm trung gian nhất không? Chỉ ra hành trình đó.
Lời giải:
Dựa vào mô tả của đồ thị trong Hình 1, có một hành trình từ địa điểm D đến địa điểm G với ít địa điểm trung gian nhất. Hành trình ngắn nhất là:
Hành trình từ D đến G:
Đi từ D -> E
Tiếp tục từ E -> G
Đây là hành trình tối ưu nhất với chỉ một địa điểm trung gian là E. Đường đi này giúp rút ngắn thời gian và quãng đường di chuyển giữa hai địa điểm D và G.
Câu hỏi trang 61 Chuyên đề Tin 12 Chân trời
Hãy cho biết thứ tự duyệt các đỉnh với phương pháp duyệt đồ thị theo chiều rộng xuất phát từ đỉnh X của đồ thị G, ở Hình 2.
Lời giải:
Dựa vào mô tả của “Hình 2. Đồ thị G,” để thực hiện duyệt đồ thị theo chiều rộng (BFS) bắt đầu từ đỉnh X, ta sẽ thăm tất cả các đỉnh kề với X trước khi chuyển sang các đỉnh khác. Một thứ tự duyệt có thể là:
Bắt đầu từ X
Duyệt đến A, B, C, D, E, F, H, K, G
Lưu ý rằng có thể có nhiều thứ tự duyệt đúng do cách chọn đỉnh kề khi duyệt có thể khác nhau. Thứ tự trên giả định rằng khi có nhiều đỉnh kề chưa được thăm, chúng ta sẽ thăm theo thứ tự bảng chữ cái.
Câu hỏi trang 62 Chuyên đề Tin 12 Chân trời
Từ đồ thị G1 trong Hình 1. Hãy thực hiện yêu cầu sau:
a. Dùng thuật toán duyệt đồ thị theo chiều rộng để tìm đường đi ngắn nhất từ đỉnh C đến tất cả các đỉnh của đồ thị.
b. Từ câu a, mô tả cách duyệt cây theo chiều rộng bắt đầu từ đỉnh C.
Lời giải:
a. Để tìm đường đi ngắn nhất từ đỉnh C đến tất cả các đỉnh khác trong đồ thị G1 bằng thuật toán duyệt theo chiều rộng (BFS), ta thực hiện các bước sau:
Bắt đầu từ đỉnh C.
Thăm tất cả các đỉnh kề với C trước khi chuyển sang các đỉnh ở cấp độ tiếp theo.
Tiếp tục quá trình này cho đến khi tất cả các đỉnh đều được thăm.
b. Cách duyệt cây theo chiều rộng từ đỉnh C:
Bắt đầu từ đỉnh C, thăm các đỉnh kề theo thứ tự từ trái sang phải hoặc từ trên xuống dưới.
Đảm bảo rằng mỗi cấp độ của cây được duyệt hoàn toàn trước khi chuyển sang cấp độ tiếp theo.
Ghi nhớ các đỉnh đã thăm để tránh thăm lại.
Luyện tập trang 62 Chuyên đề Tin 12 Chân trời
Cho hai đồ thị G3 (Hình 3) và G4 (Hình 4). Dùng thuật toán duyệt đồ thị theo chiều rộng để thực hiện hai yêu cầu sau:
- Liệt kê thứ tự duyệt các đỉnh của đồ thị G3 xuất phát từ đỉnh A.
- Cho biết đường đi từ đỉnh F đến đỉnh J trong đồ thị G4?
Lời giải:
Để thực hiện thuật toán duyệt đồ thị theo chiều rộng (BFS) cho đồ thị G3 và G4:
Đồ thị G3 xuất phát từ đỉnh A:
Bắt đầu từ đỉnh A.
Thăm các đỉnh kề với A theo thứ tự từ trái sang phải hoặc từ trên xuống dưới.
Tiếp tục quá trình này cho đến khi tất cả các đỉnh đều được thăm.
Đường đi từ đỉnh F đến đỉnh J trong đồ thị G4:
Xác định một chuỗi các cạnh liên kết từ F đến J.
Duyệt theo chiều rộng từ F, thăm các đỉnh kề và tiếp tục cho đến khi đến được J.
Thực hành trang 62 Chuyên đề Tin 12 Chân trời
Chương trình dưới đây duyệt đồ thị G3 (Hình 3) bắt đầu từ đỉnh B và đỉnh F. Em có nhận xét gì về thứ tự duyệt bắt đầu với đỉnh B và đỉnh F.
Lời giải:
Dựa vào mô tả hình ảnh của đồ thị G3, để duyệt đồ thị bắt đầu từ đỉnh B và đỉnh F, chúng ta sẽ sử dụng thuật toán duyệt theo chiều rộng (BFS). Thứ tự duyệt sẽ phụ thuộc vào cách các đỉnh được kết nối trong đồ thị. Khi bắt đầu từ đỉnh B, chúng ta sẽ thăm các đỉnh kề với B trước, sau đó là các đỉnh kề với những đỉnh đã thăm, và cứ tiếp tục như vậy. Tương tự, khi bắt đầu từ đỉnh F, chúng ta sẽ thăm các đỉnh kề với F theo cùng một cách thức.
Để có nhận xét chính xác về thứ tự duyệt, em cần thông tin cụ thể về cách các đỉnh được kết nối cũng như các quy tắc duyệt nếu có. Nếu bạn cung cấp thêm thông tin hoặc mã nguồn của chương trình, em có thể giúp bạn phân tích cụ thể hơn.
Code như sau:
def bft(graph, u): queue initQueue()
visited [vertices.index(u)] = True enqueue(queue, u)
while not is EmptyQueue (queue): u = dequeue(queue) print(u, end = "") for v in graph[u]:
if not visited[vertices.index(v)]:
visited[vertices.index(v)] = True enqueue(queue, v)
#Khởi tạo queue rỗng #Đánh dấu đỉnh u đã duyệt #Thêm đỉnh u vào queue #queue khác rỗng
#Lấy đỉnh u ra khỏi queue #Xử lí đỉnh u
#Xét đỉnh kề v của đỉnh u #Đỉnh v chưa duyệt
#Đánh dấu đỉnh v đã duyệt #Thêm đỉnh v vào queue
#Hàm duyệt graph dạng danh sách kề theo chiều rộng
def bfs(graph):
global visited
visited
[False] * len(graph)
for u in graph:
if not visited [vertices.index(u)]:
bft (graph, u)
#Đánh dấu các đỉnh chưa duyệt #Xét đỉnh u
#Đỉnh u chưa duyệt
#Duyệt đô thị từ đỉnh u
graph, vertices = createAdjListGraph('dothi.txt')
bfs (graph)
#Tạo đồ thị từ tập
Vận dụng trang 63 Chuyên đề Tin 12 Chân trời
Viết chương trình đếm số nước liên minh với nước đã cho
Yêu cầu: Có N nước, các nước được chia thành các liên minh. Quan hệ liên minh như sau:
nếu nước A liên minh với nước B, nước B liên minh với nước C thì nước A liên minh với nước C. Cho biết nước X, sử dụng thuật toán duyệt đồ thị theo chiều rộng, hãy cho biết có bao nhiêu nước liên minh với nước X.
Dữ liệu vào: Tệp lienminh.txt chứa dữ liệu của các nước. Hàng đầu tiên là danh sách các nước. Các hàng kế tiếp: mỗi hàng chứa một cạnh gồm hai nước liên minh. Hàng cuối cùng là nước X.
Dữ liệu ra: Số nước liên minh với nước X.
Lời giải:
Để giải quyết bài toán này, chúng ta sẽ sử dụng thuật toán duyệt đồ thị theo chiều rộng (BFS - Breadth-First Search). Thuật toán này sẽ giúp chúng ta xác định số lượng nước liên minh với nước X từ dữ liệu đã cho.
Các bước giải quyết bài toán:
Đọc dữ liệu từ file: Đọc danh sách các nước và các liên minh từ tệp lienminh.txt. Hàng đầu tiên là danh sách các nước, các hàng tiếp theo là các cặp nước liên minh, và hàng cuối cùng là nước X cần xác định số nước liên minh.
Biểu diễn đồ thị: Sử dụng một danh sách kề để lưu trữ các nước liên minh với nhau.
Duyệt đồ thị bằng BFS: Bắt đầu từ nước X, sử dụng BFS để duyệt qua tất cả các nước liên minh và đếm số lượng nước liên minh này.
Xuất kết quả: In ra số lượng nước liên minh với nước X.
Dưới đây là mã Python để giải quyết bài toán:
from collections import defaultdict, deque
def read_graph_data(filename):
adjacency_list = defaultdict(list)
start_node = None
with open(filename, 'r') as f:
lines = f.readlines()
countries = lines[0].strip().split()
for line in lines[1:]:
if line.strip() == '':
continue
node1, node2 = line.strip().split()
if start_node is None:
start_node = node1
adjacency_list[node1].append(node2)
adjacency_list[node2].append(node1)
x_country = lines[-1].strip()
return countries, adjacency_list, x_country
def bfs_count_connected(adjacency_list, start_node):
visited = set()
queue = deque([start_node])
visited.add(start_node)
count = 0
while queue:
node = queue.popleft()
count += 1
for neighbor in adjacency_list[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return count
def main():
filename = 'lienminh.txt'
countries, adjacency_list, x_country = read_graph_data(filename)
if x_country not in adjacency_list:
print(f"Nước {x_country} không có trong danh sách các nước liên minh.")
return
num_connected_countries = bfs_count_connected(adjacency_list, x_country)
print(f"Số nước liên minh với nước {x_country} là: {num_connected_countries}")
if __name__ == "__main__":
main()
