Câu hỏi:
04/10/2024 108
Nhiệm vụ 1. Chương trình tìm đường đi bằng thuật toán duyệt đồ thị theo chiều rộng
Yêu cầu: Cho đồ thị vô hướng G. Hãy viết chương trình tìm đường đi từ đỉnh u đến đỉnh v bằng thuật toán duyệt đồ thị theo chiều rộng. Đô thị G được biểu diễn bằng danh sách kể. Dữ liệu vào:
- Tệp dothi.txt chứa dữ liệu của đồ thị. Hàng đầu tiên là danh sách các đỉnh của đồ thị. Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn.
– Đỉnh u và đỉnh v của đường đi.
Dữ liệu ra:
– Nếu có đường đi từ đỉnh u đến đỉnh v thì hiển thị các đỉnh của đường đi này. – Nếu không có đường đi thì hiển thị "Không có đường đi".
Nhiệm vụ 1. Chương trình tìm đường đi bằng thuật toán duyệt đồ thị theo chiều rộng
Yêu cầu: Cho đồ thị vô hướng G. Hãy viết chương trình tìm đường đi từ đỉnh u đến đỉnh v bằng thuật toán duyệt đồ thị theo chiều rộng. Đô thị G được biểu diễn bằng danh sách kể. Dữ liệu vào:
- Tệp dothi.txt chứa dữ liệu của đồ thị. Hàng đầu tiên là danh sách các đỉnh của đồ thị. Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn.
– Đỉnh u và đỉnh v của đường đi.
Dữ liệu ra:
– Nếu có đường đi từ đỉnh u đến đỉnh v thì hiển thị các đỉnh của đường đi này. – Nếu không có đường đi thì hiển thị "Không có đường đi".
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Sử dụng thuật toán duyệt đồ thị theo chiều rộng, bắt đầu từ đỉnh u. Em xây dựng mảng một chiều before với giá trị mặc định của các phần tử là −1 để lưu lại các đỉnh trong quá trình duyệt với quy ước: before[i] = j nghĩa là duyệt đỉnh j trước rồi duyệt đỉnh i sau.
Chương trình tìm đường đi sử dụng thuật toán duyệt đồ thị theo chiều rộng:
def initQueue(): return []
def isEmptyQueue(queue): return len(queue) == 0 def enqueue(queue, val): queue.append(val)
def dequeue(queue): return queue.pop(0)
#Hàm xuất đường đi
def printPath(path, u, v): if path == None:
print("Không có đường đi từ đỉnh", ", "đến đỉnh", v)
else:
print("Đường đi từ đỉnh", U, "đến đỉnh", V, "là:") for v in path:
print(v, end = "")
. #Hàm tạo đường đi - def createPath(u, v): path = []
j = v
path.append(j)
while before [vertices.index(j)] != u: path.append(before[vertices.index(j)]) before[vertices.index(j)]
j
path.append(u)
path.reverse()
return path
. #Tìm đường đi từ đỉnh u đến đỉnh v trong đồ thị dùng BFS . #Hàm tìm đường đi giữa u và v sử dụng BFS
def findPathBFS (graph, u, v): queue initQueue() enqueue(queue, u)
#Khởi tạo hàng đợi queue
#Thêm đỉnh u vào queue và đánh dấu đã duyệt
visited [vertices.index(u)] = True
#Lập cho đến khi queue rỗng
while not isEmptyQueue(queue):
p dequeue (queue)
“Nếu đỉnh kể với p là v thì trả kết quả đường đi từ u đến v. Ngược lại, Em các đỉnh kề với p vào queue
for neighbor in graph[p]:
if neighbor == V:
before[vertices. index (neighbor)] = p return createPath(u, v)
elif not visited[vertices.index(neighbor)]: visited[vertices.index (neighbor)] = True enqueue(queue, neighbor)
before[vertices. index (neighbor)] = p
#Nếu không tìm thấy đường đi từ u đến v, trả về None. if before[vertices.index(v)] = -1:
return None
- #Hàm tìm đường đi từ đỉnh u đến đỉnh v def findPath(graph, u, v):
if not u in graph: print("Không có đỉnh",u)
Return đánh", ngời sáng tạo
elif not v in graph: print("Không có đỉnh ", v)
return
global visited, before
visited [False] * len(graph) before = [-1] * len(graph)
path = findPathBFS (graph, u, v) return path
graph, vertices = createAdjListGraph('dothi.txt') #Tạo đồ thị dạng danh sách kề từ tập
u, v = list(map(str, input().split()))
path findPath(graph, u, v)
print(path)
printPath(path, u, v)
Kết quả:
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Nhiệm vụ. Đếm số thành phần liên thông của đồ thị
Một đô thị G được gọi là không liên thông nếu tổn tại đỉnh u và đỉnh v thuộc G mà không có đường đi giữa hai đỉnh này. Khi đó, đỉnh u và đỉnh v thuộc hai thành phần liên thông khác nhau. Nếu tồn tại đường đi giữa đỉnh u và đỉnh v thì hai đỉnh này phải thuộc cùng một thành phần liên thông. Như vậy, đô thị G không liên thông sẽ có ít nhất hai thành phần liên thông. Yêu cầu: Cho đồ thị vô hướng G được biểu diễn bằng danh sách kể. Hãy viết chương trình cho biết số thành phần liên thông của đô thị G.
Dữ liệu vào: Tệp dothi.txt chứa dữ liệu của đô thị G. Hàng đầu tiên là danh sách các đỉnh của đô thị. Các hàng kế tiếp: mỗi hàng chứa một cạnh gồm hai đỉnh.
Dữ liệu ra: Số thành phần liên thông của đô thị G.
Dữ liệu vào dữ liệu ra tương ứng với đồ thị G1 như sau:
Nhiệm vụ. Đếm số thành phần liên thông của đồ thị
Một đô thị G được gọi là không liên thông nếu tổn tại đỉnh u và đỉnh v thuộc G mà không có đường đi giữa hai đỉnh này. Khi đó, đỉnh u và đỉnh v thuộc hai thành phần liên thông khác nhau. Nếu tồn tại đường đi giữa đỉnh u và đỉnh v thì hai đỉnh này phải thuộc cùng một thành phần liên thông. Như vậy, đô thị G không liên thông sẽ có ít nhất hai thành phần liên thông. Yêu cầu: Cho đồ thị vô hướng G được biểu diễn bằng danh sách kể. Hãy viết chương trình cho biết số thành phần liên thông của đô thị G.
Dữ liệu vào: Tệp dothi.txt chứa dữ liệu của đô thị G. Hàng đầu tiên là danh sách các đỉnh của đô thị. Các hàng kế tiếp: mỗi hàng chứa một cạnh gồm hai đỉnh.
Dữ liệu ra: Số thành phần liên thông của đô thị G.
Dữ liệu vào dữ liệu ra tương ứng với đồ thị G1 như sau:
Xem đáp án »
04/10/2024
138
Câu 2:
Chương trình tìm đường đi bằng thuật toán duyệt đô thị theo chiều sâu
Yêu cầu: Cho đồ thị G. Hãy viết chương trình tìm đường đi từ đỉnh u đến đỉnh v bằng thuật toán duyệt đồ thị theo chiều sâu. Đồ thị G được biểu diễn bằng danh sách kể.
Dữ liệu vào:
- Tệp dothi.txt chứa dữ liệu của đồ thị. Hàng đầu tiên là danh sách các đỉnh của đô thị. Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn.
– Đỉnh u và đỉnh v của đường đi.
Dữ liệu ra:
– Nếu có đường đi từ đỉnh u đến đỉnh v thì hiển thị các đỉnh của đường đi này. – Nếu không có đường đi thì hiển thị "Không có đường đi".
Chương trình tìm đường đi bằng thuật toán duyệt đô thị theo chiều sâu
Yêu cầu: Cho đồ thị G. Hãy viết chương trình tìm đường đi từ đỉnh u đến đỉnh v bằng thuật toán duyệt đồ thị theo chiều sâu. Đồ thị G được biểu diễn bằng danh sách kể.
Dữ liệu vào:
- Tệp dothi.txt chứa dữ liệu của đồ thị. Hàng đầu tiên là danh sách các đỉnh của đô thị. Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn.
– Đỉnh u và đỉnh v của đường đi.
Dữ liệu ra:
– Nếu có đường đi từ đỉnh u đến đỉnh v thì hiển thị các đỉnh của đường đi này. – Nếu không có đường đi thì hiển thị "Không có đường đi".
Xem đáp án »
04/10/2024
105
Câu 3:
Tìm đường di bằng thuật toán duyệt đồ thị theo chiều sâu
Yêu cầu; Cho bản đó (Hình 2) gồm các thành phố M, N, P, Q, R được biểu diễn bởi đồ thị. Dựa vào thuật toán duyệt đồ thị theo chiều sâu được biểu diễn bằng ma trận kể, viết chương trình in ra màn hình đường đi từ thành phố M đến thành phố R.
Dữ liệu vào: Tệp dothitxt chứa dữ liệu của đô thị. Hàng đầu tiên là danh sách các đỉnh của đô thị. Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn. Dữ liệu ra: Các dỉnh của đường di từ dỉnh M đến dỉnh R
Tìm đường di bằng thuật toán duyệt đồ thị theo chiều sâu
Yêu cầu; Cho bản đó (Hình 2) gồm các thành phố M, N, P, Q, R được biểu diễn bởi đồ thị. Dựa vào thuật toán duyệt đồ thị theo chiều sâu được biểu diễn bằng ma trận kể, viết chương trình in ra màn hình đường đi từ thành phố M đến thành phố R.
Dữ liệu vào: Tệp dothitxt chứa dữ liệu của đô thị. Hàng đầu tiên là danh sách các đỉnh của đô thị. Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn. Dữ liệu ra: Các dỉnh của đường di từ dỉnh M đến dỉnh R
Xem đáp án »
04/10/2024
82
Câu 4:
Tìm đường đi bằng thuật toán duyệt đô thị theo chiều rộng
Yêu cầu: Bản đồ mô tả đường đi giữa các địa điểm du lịch trong một thành phố được biểu diễn như ở Hình 1. Dựa vào thuật toán duyệt đồ thị theo chiều rộng được biểu diễn bằng ma trận kể, em hãy viết chương trình tìm đường đi từ địa điểm A đến địa điểm D sao cho đi qua ít địa điểm nhất.
Dữ liệu vào: Tệp dothi.txt chứa dữ liệu của đồ thị. Hàng đầu tiên là danh sách các đỉnh của đồ thị. Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn.
Dữ liệu ra: Các đỉnh của đường đi từ đỉnh A đến đỉnh D.
Tìm đường đi bằng thuật toán duyệt đô thị theo chiều rộng
Yêu cầu: Bản đồ mô tả đường đi giữa các địa điểm du lịch trong một thành phố được biểu diễn như ở Hình 1. Dựa vào thuật toán duyệt đồ thị theo chiều rộng được biểu diễn bằng ma trận kể, em hãy viết chương trình tìm đường đi từ địa điểm A đến địa điểm D sao cho đi qua ít địa điểm nhất.
Dữ liệu vào: Tệp dothi.txt chứa dữ liệu của đồ thị. Hàng đầu tiên là danh sách các đỉnh của đồ thị. Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn.
Dữ liệu ra: Các đỉnh của đường đi từ đỉnh A đến đỉnh D.
Xem đáp án »
04/10/2024
74
Bình luận
🔥 Đề thi HOT:
-
263 câu Trắc nghiệm tổng hợp ôn thi tốt nghiệp THPT môn Tin học Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính có đáp án
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 7: HTML và cấu trúc trang web
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 10: Tạo liên kết
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 8: Định dạng văn bản
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 11: Chèn tệp tin đa phương tiện và khung nội tuyến vào trang web
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 9: Tạo danh sách, bảng
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Bài 1: Làm quen với ngôn ngữ đánh dấu siêu văn bản
-
Đề thi Học kì 1 Tin học 12 có đáp án (Đề 1)
về câu hỏi!