Câu hỏi:

04/10/2024 120

Nhiệm vu: Duyệt đồ thị theo chiều sâu

Yêu cầu: Chương trình sau được viết bằng Phython duyệt đồ thị theo chiều sâu, với đồ thị Graph được biểu diễn bằng danh sách kề.

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

a) Biểu diễn đồ thị G4 thành danh sách kề.

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

b) Thực hiện chạy chương trình trên để duyệt đồ thị G4 được biểu diễn bằng danh sách kề.

c) Thực hiện chạy chương trình trên để duyệt đồ thị G4, được biểu diễn bằng danh sách kề, bắt đầu từ đỉnh 3.

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

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

1

 

 

 

 

 

Đã duyệt

 

1

 

Stack

 

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

1

7

 

 

 

 

Đã duyệt

 

7

1

 

Stack

 

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

1

7

2

 

 

 

Đã duyệt

 

2

7

1

 

Stack

 

 

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

1

7

2

3

 

 

Đã duyệt

 

3

2

7

1

 

Stack

 

 

 

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

1

7

2

3

4

 

Đã duyệt

 

4

3

2

7

1

 

Stack

 

 

 

 

6. Xem đỉnh 4 ở đỉnh ngăn xếp. Đỉnh kề 4 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 4 ra khỏi ngăn xếp ngăn xếp.

1

7

2

3

4

 

Đã duyệt

 

3

2

7

1

 

Stack

 

 

 

7. Xem đỉnh 3 ở đỉnh ngăn xếp. Đỉnh kề 5 của đỉnh kề 3 chưa duyệt. Duyệt đỉnh 5 vào ngăn xếp.

1

7

2

3

4

5

 

Đã duyệt

 

5

3

2

7

1

 

Stack

 

 

 

 

8. Xem đỉnh 7 ở đỉnh ngăn xếp. Đỉnh kề 6 của đỉnh kề 7 chưa được duyệt. Duyệt  đỉnh 6 ra vào ngăn xếp.

1

7

2

3

4

5

6

 

Đã duyệt

 

6

3

2

7

1

 

Stack

 

9. Xem đỉnh 6 ở đỉnh ngăn xếp. Đỉnh kề 6 không có đỉnh kề nào chưa duyệt. Lấy đỉnh  6 ra khỏi ngăn xếp.

1

7

2

3

4

5

6

Đã duyệt

 

3

2

7

1

 

Stack

 

 

 

 

10. Xem đỉnh 7 ở đỉnh ngăn xếp. Đỉnh kề 8 của đỉnh kề 7 chưa duyệt. Duyệt đỉnh 8 vào ngăn xếp.

1

7

2

3

4

5

6

8

Đã duyệt

 

8

3

2

7

1

 

Stack

 

 

 

 

11. Xem đỉnh 8 ở đỉnh ngăn xếp. Đỉnh kề 8 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 8 ra khỏi ngăn xếp.

1

7

2

3

4

5

6

8

Đã duyệt

 

3

2

7

1

 

Stack

 

 

 

12. Xem đỉnh 3 ở đỉnh ngăn xếp. Đỉnh kề 3 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 3 ra khỏi ngăn xếp.

1

7

2

3

4

5

6

8

Đã duyệt

 

2

7

1

 

Stack

 

 

13. Xem đỉnh 2 ở đỉnh ngăn xếp. Đỉnh kề 2 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 2 ra khỏi ngăn xếp.

1

7

2

3

4

5

6

8

Đã duyệt

 

7

1

 

Stack

 

14. Xem đỉnh 7 ở đỉnh ngăn xếp. Đỉnh kề 7 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 7 ra khỏi ngăn xếp.

1

7

2

3

4

5

6

8

Đã duyệt

 

1

 

Stack

 

15. Xem đỉnh 1 ở đỉnh ngăn xếp. Đỉnh kề 1 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 7 ra khỏi ngăn xếp.

1

7

2

3

4

5

6

8

Đã duyệt

 

Stack

16. Ngăn xếp rỗng. Kết thúc. Thứ tự duyệt đồ thị theo chiều sâu là:

1

7

2

3

4

5

6

8

Đã duyệt

 

 

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.

Nâng cấp VIP

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.

Nâng cấp VIP

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.

Nâng cấp VIP