Câu hỏi:
04/10/2024 179
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".
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ả:
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:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
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ể. Viết chương trình cho biết số thành phần liên thông của đô thị G.
def dfs(G, u):
Xử lí đỉnh u
Đánh dấu duyệt đỉnh u
for đỉnh v là đỉnh kế của đỉnh u:
if đỉnh v chưa được đánh dấu duyệt: dfs(G, v)
Thuật toán duyệt đô thị theo chiều sâu bắt đầu từ đỉnh u:
def dft(G, u):
Khởi tạo ngăn xếp stack rỗng
Xử lí đỉnh u
Đánh dấu duyệt đỉnh u
Thêm đỉnh u vào ngăn xếp stack while ngăn xếp stack khác rỗng:
Xem đỉnh p ở đầu ngăn xếp stack
#Xét các đỉnh kề v chưa được duyệt của đình p found False
for đỉnh v thuộc tập đỉnh kề của đỉnh p: if đỉnh v chưa duyệt:
found=True break
if not found:
Lấy đỉnh p ra khỏi ngăn xếp stack
else:
Xử lí đỉnh v
Đánh dấu duyệt đỉnh v
Thêm đỉnh v vào ngăn xếp stack
Thuật toán duyệt theo chiều sâu các đỉnh của đô thị G được minh hoạ như sau:
def dfs(G):
for đỉnh u thuộc G.
Đánh dấu đỉnh u chưa duyệt.
For đỉnh u thuộc G.
If đỉnh u chưa duyệt
Dft(G,u)
Lời giải
Thuật toán duyệt đô thị theo chiều rộng:
#Duyệt đồ thị G bắt đầu từ đỉnh u def bft (G, u):
đại anh từ trời sáng tạo
Tạo hàng đợi 2 rỗng
Đánh dấu đỉnh u đã duyệt Thêm đỉnh u vào hàng đợi Q while hàng đợi Q khác rỗng: Lấy đính u từ hàng đợi Q xử lí đỉnh
#Thêm các đỉnh kề v của đỉnh u vào hàng đợi a for đỉnh v thuộc tập đỉnh kề của đỉnh u:
if đỉnh v chưa duyệt:
Đánh dấu đỉnh v đã duyệt
Thêm đỉnh v vào hàng đợi Q
Khi đó, thủ tục thực hiện duyệt đồ thị G = (V, E) theo chiều rộng như sau:
#Duyệt đồ thị G theo chiều rộng
def bfs (G):
#Đánh dấu các đỉnh của đồ thị G chưa duyệt
for đỉnh u thuộc đô thị G:
Đánh dấu đỉnh u chưa duyệt
#Duyệt các đỉnh của đồ thị G for đỉnh u thuộc của đô thị 6: if đỉnh u chưa duyệt:
bft (G, u)
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
🔥 Đề thi HOT:
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Mô hình và các giao thức mạng có đáp án
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Giới thiệu trí tuệ nhân tạo có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 23 có đáp án
-
Bộ 3 đề thi cuối kì 2 Tin 12 Kết nối tri thức có đáp án - Đề 2
-
Bộ 3 đề thi cuối kì 2 Tin 12 Chân trời sáng tạo có đáp án - Đề 3
-
Bộ 3 đề thi cuối kì 2 Tin 12 Kết nối tri thức có đáp án - Đề 1
-
Bộ 3 đề thi cuối kì 2 Tin 12 Cánh diều có đáp án - Đề 2
-
Bộ 3 đề thi cuối kì 2 Tin 12 Chân trời sáng tạo có đáp án - Đề 2