Tìm đường di bằng thuật toán duyệt đồ thị theo chiều sâu
Yêu cầu; Cho bản đó (Hình 2) gồm các thành phố M, N, P, Q, R được biểu diễn bởi đồ thị. Dựa vào thuật toán duyệt đồ thị theo chiều sâu được biểu diễn bằng ma trận kể, viết chương trình in ra màn hình đường đi từ thành phố M đến thành phố R.
Dữ liệu vào: Tệp dothitxt chứa dữ liệu của đô thị. Hàng đầu tiên là danh sách các đỉnh của đô thị. Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn. Dữ liệu ra: Các dỉnh của đường di từ dỉnh M đến dỉnh R
Quảng cáo
1 câu trả lời 10
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)
Quảng cáo
Bạn cần hỏi gì?
Câu hỏi hot cùng chủ đề
-
Đã trả lời bởi chuyên gia
149512 -
Đã trả lời bởi chuyên gia
99915 -
Đã trả lời bởi chuyên gia
97515 -
Đã trả lời bởi chuyên gia
80194 -
Đã trả lời bởi chuyên gia
73007 -
Đã trả lời bởi chuyên gia
56101 -
Đã trả lời bởi chuyên gia
55469
