Question

Đã trả lời bởi chuyên gia

Answer 1

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.

...Xem thêm

Answer 2