khoahoc.vietjack.com
Xin chào! Vào học

Câu hỏi:

04/10/2024 365 Lưu

Cho đồ thị G5 (Hình 5). Chỉ ra đường đi từ đỉnh F đến đỉnh J bằng thuật toán duyệt đồ thị theo chiều sâu trong đồ thị G5.

Media VietJack

Quảng cáo

Trả lời:

verified Giải bởi Vietjack

1. Duyệt đỉnh F, thêm đỉnh F vào ngăn xếp

F

 

 

 

 

 

Đã duyệt

 

F

 

Stack

 

2. Xem đỉnh F ở đỉnh ngăn xếp. Đỉnh kề B của đỉnh F chưa duyệt. Duyệt đỉnh B thêm đỉnh này vào ngăn xếp.

F

B

 

 

 

 

Đã duyệt

 

B

F

 

Stack

 

3. Xem đỉnh B ở đỉnh ngăn xếp. Đỉnh kề H của đỉnh B chưa duyệt. Duyệt đỉnh H thêm đỉnh này vào ngăn xếp.

F

B

H

 

 

 

Đã duyệt

 

H

B

F

 

Stack

 

 

3. Xem đỉnh H ở đỉnh ngăn xếp. Đỉnh kề J của đỉnh H chưa duyệt. Duyệt đỉnh J thêm đỉnh này vào ngăn xếp.

F

B

H

J

 

 

Đã duyệt

 

J

H

B

F

 

Stack

 

 

 

Đang tải chế độ Học...

Dành cho bạn Hot

Lớp 12 Vật lý
210 người thi tuần này

Trắc nghiệm Mô hình động học phân tử chất khí lớp 12 (có đáp án)

15 câu 1.9 K lượt thi Thi ngay →
Lớp 12 Tiếng Anh
138 người thi tuần này

Đề cương ôn tập giữa kì 1 Tiếng Anh 12 Global Success có đáp án

45 câu 1.3 K lượt thi Thi ngay →
Lớp 12 Sinh học
158 người thi tuần này

10 câu trắc nghiệm Sinh học 12 Kết nối tri thức Bài 8 có đáp án

10 câu 2 K lượt thi Thi ngay →
Lớp 12 Lịch sử
2,339 người thi tuần này

20 câu trắc nghiệm Lịch sử 12 Kết nối tri thức Bài 1 có đáp án

20 câu 22.4 K lượt thi Thi ngay →
Lớp 12 Địa lý
406 người thi tuần này

20 câu Trắc nghiệm Địa lý 12 Kết nối tri thức Bài 2 có đáp án

25 câu 6 K lượt thi Thi ngay →
Lớp 12 Tin học
574 người thi tuần này

15 câu Trắc nghiệm Tin học 12 Kết nối tri thức có đáp án

15 câu 13.2 K lượt thi Thi ngay →
Lớp 12 Giáo dục Kinh tế và Pháp luật
656 người thi tuần này

15 Câu trắc nghiệm KTPL 12 Kết nối tri thức Bài 1 có đáp án

15 câu 8.9 K lượt thi Thi ngay →

CÂU HỎI HOT CÙNG CHỦ ĐỀ

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

Cho đồ thị G1 như ở Hình 1. Tìm đường đi ngắn nhất từ đỉnh H đến đỉnh D bằng thuật toán duyệt đồ thị theo chiều rộng như sau:

Media VietJack

 

Media VietJack

Media VietJack

Media VietJack

 

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Xem trọn bộ đề thi 6 câu hỏi
Xem thêm