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

Trang trước Trang sau

Nhiệm vụ 1 trang 72 Chuyên đề Tin học 12: 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".

Lời giải:

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ả:

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

Lời giải bài tập Chuyên đề Tin 12 Bài 3.5: Thực hành kĩ thuật duyệt đồ thị hay, chi tiết khác:

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Chân trời sáng tạo hay, chi tiết khác:

Xem thêm các tài liệu học tốt lớp 12 hay khác:

Trang trước Trang sau
Giải bài tập lớp 12 sách mới các môn học