Đưa đỉnh chờ xét vào stack
Bản không đệ quy dùng S như ngăn xếp: append thêm ở đỉnh, pop lấy đỉnh. Khi lấy một đỉnh đã seen thì bỏ qua; đỉnh chưa seen được đánh dấu và đưa vào order. Các đỉnh kề chưa thăm được đẩy theo thứ tự trong Adj.
```python
def dfs_stack(Adj, s):
check_vertex(Adj, s)
seen = [False]*len(Adj)
order = []
S = [s]
while S:
u = S.pop()
if seen[u]:
continue
seen[u] = True
order.append(u)
for v in Adj[u]:
if not seen[v]:
S.append(v)
return order
```
Đẩy 1 rồi 2 nhưng lấy 2 trước
Với mẫu, sau khi lấy 0, đẩy 1 rồi 2, S=[1,2]. Lần kế tiếp lấy 2 vì LIFO. Thứ tự phát hiện của mã là **0,2,4,5,3,1**.
|Sau khi phát hiện|S, đáy đến đỉnh|
|---|---|
|0|[1,2]|
|2|[1,4]|
|4|[1,1,5]|
|5|[1,1,3]|
|3|[1,1,1]|
Đỉnh 1 có thể được đẩy nhiều lần trước khi được lấy ra lần đầu. Nhánh kiểm seen giúp order chỉ có một lần 1. Không đồng nhất số lần pop với số đỉnh mới phát hiện.
Đây vẫn là DFS, nhưng thứ tự khác bản đệ quy xét kề tăng dần. Nếu muốn ưu tiên đỉnh nhỏ bằng stack, có thể đẩy các đỉnh kề theo thứ tự ngược; cần đối chiếu quy tắc đẩy và thời điểm đánh dấu của chính phiên bản đang dùng.
Bài luyện
Sau khi xét 0, S=[1,2], đỉnh ở cuối. Lần pop kế tiếp nhận gì?
Đúng. Ngăn xếp lấy cuối theo LIFO.
1 được đẩy trước và nằm dưới 2.
0 đã được lấy ra.
Mỗi pop chỉ lấy một phần tử.
Lời giải
S biểu diễn đáy đến đỉnh nên 2 ở đỉnh. pop() lấy phần tử cuối là 2; 1 vẫn chờ trong ngăn xếp.
Bài luyện
S có ba số 1 đang chờ. Vì sao order chỉ ghi 1 một lần?
List cho phép phần tử trùng.
pop chỉ lấy một phần tử.
Đúng. seen quyết định có phát hiện mới hay không.
Mã không sửa Adj.
Lời giải
Lần đầu lấy 1 khi seen[1] còn False, mã đặt True và thêm 1 vào order. Những lần sau seen[1] đã True nên continue, không thêm lại.
Bài luyện
Bản stack của bài cho thứ tự nào từ 0?
Đây là BFS mẫu.
Đúng. Các đỉnh đẩy sau được lấy trước.
Đây là DFS đệ quy mẫu.
Một lượt từ 0 không tới 6.
Lời giải
Lấy 0, ưu tiên 2 vì được đẩy sau 1; rồi đi 4,5,3,1. Các lần gặp lại đỉnh đã seen bị bỏ qua, nên order là 0,2,4,5,3,1.
Đang học