Quảng cáo
Trả lời:
Giải bởi Vietjack
Hai thuật toán duyệt đồ thị theo chiều rộng (BFS) và chiều sâu (DFS) là hai thuật toán cơ bản nhất của đồ thị. Các thuật toán này giúp chúng ta “đến thăm” tất cả các cạnh và các đỉnh của đồ thị trong thời gian tối thiểu. Một số bài toán như: Kiểm tra một đồ thị là phân đôi (bi-partite), Tìm đường ngắn nhất trong đồ thị không có trọng số (Single source Shortest path in an unweighted graph), Tìm vòng trong đồ thị vô hướng, Tìm vòng (cycle) trong đồ thị có hướng, Case study: Dò mìn (Minesweeper).
Hot: 1000+ Đề thi cuối kì 1 file word cấu trúc mới 2025 Toán, Văn, Anh... lớp 1-12 (chỉ từ 60k). 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
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ạ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.
Nhắn tin Zalo
Hỏi bài tập