Chương trình tìm đường đi bằng thuật toán duyệt đô thị theo chiều sâu

Giải Chuyên đề Tin 12 Bài 3.5: Thực hành kĩ thuật duyệt đồ thị - Chân trời sáng tạo

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

Lời giải:

Sử dụng thuật toán duyệt đồ thị theo chiều sâu để tiến hành duyệt tất cả các đỉnh mà u có thể liên kết tới trong đồ thị. 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 đến đỉnh i

def initStack(): return []

def isEmptyStack(stack): return len(stack) == 0 def push(stack, val): stack.append(val) def pop(stack):

return stack.pop() def top(stack):

return stack[len(stack).

ack Rentstack)-Thi sáng tạo

#Tìm đường đi từ đỉnh u đến đỉnh v trong đồ thị dùng DFS #Hàm tìm đường đi giữa u và v sử dụng DFS

def findPathDFS (graph, u, v):

stack = initStack() #Khởi tạo ngăn xếp stack

push(stack, u) #Thêm đỉnh ũ vào stack và đánh dấu đã duyệt visited [vertices.index(u)] = True

#Lập cho đến khi stack rằng while not isEmptyStack(stack): p = top(stack)

found = False

for neighbor in graph[p]:

if not visited[vertices.index(neighbor)]: found = True

break

if found:

visited [vertices.index(neighbor)] = True before [vertices.index(neighbor)] = p if neighbor V:

return createPath(u, v)

else:

else:

push(stack, neighbor)

p = pop(stack)

#Nếu không tìm thấy đường đi từ u đến v, 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

elif not v in graph:

print("Không có đỉnh ", v)

return

global visited, before

visited [False] * len(graph) before [-1] * len(graph)

=

=

path findPathDFS (graph, u, v) return path

#ví dụ minh hoạ

trả về None.

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

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:

• Khởi động trang 72 Chuyên đề Tin học 12: Nêu một ứng dụng của một trong hai thuật toán duyệt đồ thị đã học ....

• 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 ....

• Nhiệm vụ 1 trang 75 Chuyên đề Tin học 12: Tìm đường đi bằng thuật toán duyệt đô thị theo chiều rộng ....

• Nhiệm vụ 2 trang 76 Chuyên đề Tin học 12: Tìm đường di bằng thuật toán duyệt đồ thị theo chiều sâu ....

• Vận dụng trang 76 Chuyên đề Tin học 12: Nhiệm vụ. Đếm số thành phần liên thông của đồ thị ....

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:

• Chuyên đề Tin 12 Bài 2.4: Thực hành cây tìm kiếm nhị phân

• Chuyên đề Tin 12 Bài 3.1: Các khái niệm cơ bản của đồ thị

• Chuyên đề Tin 12 Bài 3.2: Biểu diễn đồ thị

• Chuyên đề Tin 12 Bài 3.3: Duyệt đồ thị theo chiều rộng

• Chuyên đề Tin 12 Bài 3.4: Duyệt đồ thị theo chiều sâu

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

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều

---