Câu hỏi:

26/06/2024 137

Viết lại hàm BFS() trong chương trình trên nhưng sử dụng ma trận kề A thay thế cho danh sách kề Adj.

Xem lời giải

Câu hỏi trong đề: Giải chuyên đề Tin 12 KNTT Bài 17: Thực hành duyệt đồ thị tổng hợp có đáp án !!

Bắt đầu thi

Quảng cáo

Trả lời:

Giải bởi Vietjack

Viết lại hàm BFS sử dụng ma trận kề A thay vì danh sách kề Adj. Dưới đây là cách triển khai:

from collections import deque

def BFS(graph, start):

n = len(graph)

visited = [False] * n

visited[start] = True

queue = deque([start])

while queue:

vertex = queue.popleft()

print("Visit:", vertex)

for neighbor in range(n):

if graph[vertex][neighbor] == 1 and not visited[neighbor]:

visited[neighbor] = True

queue.append(neighbor)

# Ma trận kề mẫu

graph_matrix = [

[0, 1, 1, 0, 0, 0],

[1, 0, 0, 1, 1, 0],

[1, 0, 0, 0, 0, 1],

[0, 1, 0, 0, 0, 0],

[0, 1, 0, 0, 0, 1],

[0, 0, 1, 0, 1, 0]

]

# Thực hiện BFS từ đỉnh 0

BFS(graph_matrix, 0)

- Trong hàm BFS này, chúng ta duyệt qua các hàng của ma trận kề để xác định các đỉnh kề của mỗi đỉnh. Nếu có một đỉnh kề chưa được duyệt, chúng ta đánh dấu đỉnh đó đã được thăm và thêm nó vào hàng đợi để duyệt tiếp.

Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay

Sách thầy cô Vietjack biên soạn:

Xem thêm »

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1

Sửa lại phần nhập dữ liệu hai học sinh: sẽ nhập trực tiếp tên hai học sinh, kiểm tra các tên này có nhập đúng không và thực hiện yêu cầu như trong chương trình trên.

Xem đáp án

Lời giải

Để sửa lại phần nhập dữ liệu để nhập trực tiếp tên hai học sinh và kiểm tra tính hợp lệ của chúng, chúng ta có thể thực hiện như sau:

Bài mẫu tổng quát gợi ý:

def input_student_names():

while True:

name1 = input("Nhập tên học sinh thứ nhất: ")

name2 = input("Nhập tên học sinh thứ hai: ")

if name1.strip() == "" or name2.strip() == "":

print("Tên học sinh không được để trống. Vui lòng nhập lại.")

elif name1 == name2:

print("Hai học sinh không thể có cùng tên. Vui lòng nhập lại.")

else:

return name1, name2

# Hàm tính tổng điểm trung bình

def calculate_average_score(score_list):

return sum(score_list) / len(score_list)

# Hàm in thông tin học sinh

def print_student_info(name, scores):

avg_score = calculate_average_score(scores)

print(f"Học sinh {name}:")

print(f" - Điểm Toán: {scores[0]}")

print(f" - Điểm Văn: {scores[1]}")

print(f" - Điểm Anh: {scores[2]}")

print(f"Điểm trung bình: {avg_score:.2f}")

# Hàm nhập điểm cho học sinh

def input_student_scores(name):

scores = []

for subject in ["Toán", "Văn", "Anh"]:

while True:

try:

score = float(input(f"Nhập điểm {subject} của học sinh {name}: "))

if score < 0 or score > 10:

print("Điểm phải nằm trong khoảng từ 0 đến 10. Vui lòng nhập lại.")

else:

scores.append(score)

break

except ValueError:

print("Điểm phải là một số thực. Vui lòng nhập lại.")

return scores

# Hàm chính

def main():

print("Nhập thông tin của hai học sinh:")

name1, name2 = input_student_names()

scores1 = input_student_scores(name1)

scores2 = input_student_scores(name2)

print("\nThông tin hai học sinh sau khi nhập:")

print_student_info(name1, scores1)

print()

print_student_info(name2, scores2)

if __name__ == "__main__":

main()

- Trong phiên bản này, chúng ta sử dụng một vòng lặp while để yêu cầu người dùng nhập tên hai học sinh. Sau đó, kiểm tra tính hợp lệ của tên đó (không được để trống và hai học sinh không thể có cùng tên). Nếu các tên được nhập đúng cách, chúng ta trả về tên của hai học sinh và tiếp tục với việc nhập điểm và in thông tin học sinh như bình thường.

Câu 2

Trong bài thực hành trước chúng ta đã được ôn tập và giải một số bài toán có áp dụng thuật toán duyệt đồ thị theo chiều sâu. Còn về thuật toán duyệt theo chiều rộng em có biết gì về các ứng dụng thực tế của bài toán này không?

Xem đáp án

Lời giải

Thuật toán duyệt đồ thị theo chiều rộng (BFS - Breadth-First Search) cũng rất hữu ích và được sử dụng trong nhiều ứng dụng thực tế. Dưới đây là một số ứng dụng phổ biến của BFS:

- Tìm kiếm ngắn nhất trong đồ thị không có trọng số

- Tìm kiếm ngắn nhất trong mạng lưới (grid)

- Tìm kiếm trạng thái

- Tính toán khoảng cách

- Kiểm tra tính liên thông của đồ thị

- Tìm kiếm trong cấu trúc dữ liệu cây

Câu 3