Nhiệm vụ. Kiểm tra đô thị liên thông Một đồ thị được gọi là liên thông nếu tồn tại
Nhiệm vụ. Kiểm tra đô thị liên thông
Giải Chuyên đề Tin 12 Bài 3.4: Duyệt đồ thị theo chiều sâu - Chân trời sáng tạo
Vận dụng trang 71 Chuyên đề Tin học 12: Nhiệm vụ. Kiểm tra đô thị liên thông
Một đồ thị được gọi là liên thông nếu tồn tại ít nhất một đường đi giữa hai đỉnh bất kì của nó. Chẳng hạn, đồ thị ở Hình 6a là liên thông còn đô thị ở Hình 6b là không liên thông (không có đường đi từ đỉnh 0 tới đỉnh 3).
Yêu cầu: Áp dụng thuật toán duyệt đồ thị theo chiều sâu. Thực hiện xây dựng thuật toán kiểm tra xem đồ thị G = (V, E) cho trước có liên thông hay không.
Lời giải:
Áp dụng thuật toán duyệt đồ thị theo chiều sâu. Thực hiện xây dựng thuật toán kiểm tra xem đồ thị G = (V, E) cho trước có liên thông hay không.
def dft(graph, u): stack initStack()
#Khởi tạo stack rỗng
visited [vertices.index(u)] = True #Đánh dấu đỉnh u đã duyệt
print(u, end = " ")
push(stack, u)
#In đỉnh u
#Thêm đỉnh u vào stack
while not isEmptyStack(stack): #Lặp khi stack khác rỗng
p = top(stack)
found = False
for v in graph[p]:
#Xem đỉnh p ở đỉnh stack
#Chưa tìm thấy
#Lặp để lấy các đỉnh kề v của đỉnh p
if not visited[vertices.index(v)]: #Nếu đỉnh v chưa duyệt
found = True
break
if not found:
p = pop(stack)
else:
#Tìm thấy
#Không tìm thấy đỉnh v
#Lấy đỉnh p ra khỏi stack
#Tìm thấy đỉnh v chưa duyệt
visited[vertices.index(v)] = True #Đánh dấu đỉnh v đã duyệt
print(v, end = "")
push(stack, v)
#In đỉnh v
#Thêm đỉnh v vào stack
#Hàm duyệt graph dạng danh sách kế theo chiều sâu
def dfs(graph):
global visited
visited [False]
*
len(graph)
for u in graph:
if not visited [vertices.index(u)]:
dft(graph, u)
#Đánh dấu các đỉnh chưa duyệt
#Xét đỉnh u chưa duyệt
#Duyệt đô thị theo chiều sâu từ u
graph, vertices = createAdjListGraph('dothi.txt') #Tạo đô thị từ tập dfs(graph)
#In kết quả duyệt theo chiều sâu
Lời giải bài tập Chuyên đề Tin 12 Bài 3.4: Duyệt đồ thị theo chiều sâu hay, chi tiết khác: