Skip to main content

BFS & DFS

Xem sơ đồ thị 🌴. Do BFS và DFS là 2 thuật toán duyệt đồ thị.

Xài khi nào?

Tìm kiếm theo chiều rộng. Dùng trên đồ thị không trọng số (vô hướng hoặc có hướng). Nếu có trọng số thì trọng số các đường đi phải giống nhau (do thuật toán chỉ đếm số cạnh đi qua).

BFS trả lời được câu hỏi:

  • có đường từ u \rightarrow v hay không?
  • tìm được đường đi ngắn nhất (nếu tồn tại)

Giới thiệu cơ chế

Tưởng tượng giống như nhỏ giọt dầu xuống, giọt dầu loang ra khắp rộng. Duyệt BFS sẽ đi tất cả đường đi có thể đi.

TODO: Giả sử với cái hình như này (14:41)

Nó sẽ đi từ đỉnh ra, đỉnh nào gần đỉnh gốc trước thì đi trước. Làm thế nào để biết phải đi đỉnh nào trước \rightarrow dùng array để lưu lại. Những điểm gần hơn thì mình cần ưu tiên xử lý hơn \rightarrow xử lý thằng nào lưu trước \rightarrow FIFO \rightarrow dùng queue.

Độ phức tạp: O(V+E)O(V + E)

*V: total of vertices E: total of edges

Cách lưu trữ

Có 3 cách:

Ma trận kề (Adjacency matrix)

Tạo ma trận vuông kích thước V2V^2. Phần tử ô [i][j][i][j] đại diện có cạnh giữa node iijj hay không (0 là không, 1 là có). Đồ thị vô hướng thì đường chéo là 0 hết.

6 (đỉnh)
0 1 0 1 0 0
1 0 1 1 0 1
0 1 0 0 0 1
1 1 0 0 1 1
0 0 0 1 0 0
0 1 1 1 0 0

Cách lưu trữ đơn giản nhưng tốn bộ nhớ. Có những cạnh không tồn tại nhưng vẫn tốn bộ nhớ để lưu nó. Khả năng truy xuất cũng kém hơn, ví dụ muốn biết node 0 kết nối với những đỉnh nào thì phải dò hết hàng 0.

Danh sách cạnh (Edge list)

Lưu theo E cạnh. Ví dụ ở đây có 8 cạnh \rightarrow lưu 8 dòng.

6 8 <- 6 đỉnh, 8 cạnh
0 1
0 3
1 2
1 3
1 5
2 5
3 4
3 5

Cách lưu tiết kiệm bộ nhớ hơn tuy nhiên vẫn chưa giải quyết vấn đề duyệt xem node đó kề với node nào. Ví dụ tìm 1 kề với cái nào? 1 kề với 0, 2, 3, 5 (ví dụ trên đã sort đẹp rồi, ví dụ không theo thứ tự đẹp thì vẫn phải duyệt toàn bộ cạnh).

Danh sách kề (Adjacency list)

Lưu theo V đỉnh. Mỗi đỉnh sẽ có 1 danh sách các đỉnh kề với nó.

0: 1 3
1: 0 2 3 5
2: 1 5
3: 0 1 4 5
4: 3
5: 1 2 3

Có thể thấy nó là cải tiến của adjacency matrix. Loại bỏ đi các số 0 dư thừa (cạnh không tồn tại). Ngoài ra, cũng trực quan cho biết node nào kề với node nào.

Cách lưu này tiết kiệm bộ nhớ nhất. Cách lưu này cũng giải quyết được vấn đề duyệt.

*Note: thứ tự danh sách kề không nhất thiết tăng dần, lưu thứ tự nào cũng được. Vì các cạnh đều sẽ đi qua.

Cài đặt

  1. Chuẩn bị dữ liệu:
  • Danh sách cạnh kề: graph
  • Mảng đánh dấu các đỉnh đã xét: visited
  • Mảng lưu đường đi: path. path[i] nghĩa là đỉnh trước đỉnh ii là đỉnh nào trong đường đi ngắn nhất từ đỉnh gốc đến đỉnh ii.
  • Queue để lưu các đỉnh cần xét: queue
  1. Khởi tạo dữ liệu:
  • visitedpath khởi tạo giá trị ban đầu là 0
  • queue khởi tạo giá trị ban đầu là đỉnh gốc
  1. Duyệt:
  • Lấy đỉnh đầu tiên trong queue ra (gần đỉnh gốc nhất)
  • Duyệt các đỉnh kề với đỉnh đó
  • Nếu đỉnh kề chưa được xét thì đánh dấu đã xét và lưu vào queue
  • Lưu đỉnh đó vào path (đỉnh trước đỉnh đó là đỉnh đầu tiên trong queue)
  • Lặp lại bước 1

Muốn biết đường đi đi như thế nào thì nhìn vào mảng path.

from queue import Queue
MAX = 100
V = None
E = None
visited = [False for i in range(MAX)]
path = [0 for i in range(MAX)]
graph = [[] for i in range(MAX)]

def BFS(s):
for i in range(V):
visited[i] = False
path[i] = -1
q = Queue()
visited[s] = True
q.put(s)
while not q.empty():
u = q.get()
for v in graph[u]:
if not visited[v]:
visited[v] = True # đôi khi có thể dùng cái khác đánh dấu mà ko cần visited luôn
q.put(v) # ví dụ cần lưu thông tin phụ thì thêm vô đây (dùng tuple)
path[v] = u # nếu bài toán ko cần tìm đường đi thì có thể bỏ

Thêm

Chứng minh đồ thị không liên thông

Khi 2 đỉnh cần tìm không có đường đi tới được nhau (ví dụ 2 đồ thị không liên thông).

Làm sao chứng minh được đường đi đó là ngắn nhất?

Hàm main

if __name__ == "__main__":
V, E = map(int, input().split())
for i in range(E):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
s = 0
f = 5
BFS(s)
printPath(s, f)

In đường đi từ mảng lưu vết

C1: Khử đệ quy:

def printPath(s, f):
b = []
if f == s:
print(s)
return
if path[f] == -1:
print("No path")
return
while True:
b.append(f)
f = path[f]
if f == s:
b.append(s)
break
for i in range(len(b) - 1, -1, -1):
print(b[i], end=" ")

C2: Dùng đệ quy:

def printPathRecursion(s, f):
if s == f:
print(f, end=" ")
else:
if path[f] == -1:
print("No path")
else:
printPathRecursion(s, path[f])
print(f, end=" ")

Xài khi nào?

Tìm kiếm theo chiều sâu. Dùng trên đồ thị không trọng số (vô hướng hoặc có hướng). Nếu có trọng số thì trọng số các đường đi phải giống nhau (do thuật toán chỉ đếm số cạnh đi qua).

DFS luôn tìm được đường đi từ 1 đỉnh bất kỳ tới 1 đỉnh bất kỳ khác. Tuy nhiên, nó không chắc chắn tìm được đường đi ngắn nhất.

\rightarrow Mục tiêu khi dùng là để xét xem có đường đi hay không thôi. Hoặc dùng hỗ trợ bài toán khác. Muốn kết quả tốt nhất thì xài BFS. Nhiều bài toán BFS hay DFS đều như nhau.

Giới thiệu cơ chế

Khác với BFS giống như nhỏ giọt nước, DFS giống như đi mê cung, khi đi thì mình không biết mình sẽ đi đâu, về đâu. Mình sẽ chọn 1 đường đi tiếp hoài tới khi đường cụt hoặc lối ra.

Độ phức tạp: O(V+E)O(V + E)

*V: total of vertices E: total of edges

Cách lưu trữ

Cài đặt

Vì DFS xài stack nên có 2 cách cài. Không dùng đệ quy (giống BFS), xài stack:

MAX = 100
V = None
E = None
visited = [False for i in range(MAX)]
path = [0 for i in range(MAX)]
graph = [[] for i in range(MAX)]

def DFS(src):
for i in range(V):
visited[i] = False
path[i] = -1
s = []
visited[src] = True
s.append(src)

while len(s) > 0:
u = s.pop()
for v in graph[u]:
if not visited[v]:
visited[v] = True
s.append(v)
path[v] = u

Dùng đệ quy:

def DFSRecursion(s):
visited[s] = True
for v in graph[s]:
if not visited[v]:
path[v] = s
DFSRecursion(v)

Note that BFS cho đường đi tốt hơn DFS stack hoặc DFS recursion. Do DFS stack & recursion sử dụng cấu trúc khác nhau nên có thể cho đường đi khác nhau (k chắc chắn stack sẽ tốt hơn recursion & ngc lại).

Thêm

Hàm main

if __name__ == "__main__":
V, E = map(int, input().split())
for i in range(E):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
s = 0
f = 5
DFS(s)
printPath(s, f)

Nếu xài DFS đệ quy thì cần khởi tạo lại mảng visitedpath trước khi gọi đệ quy (vì để trong đệ quy thì mỗi lần gọi lại reset trạng thái)

if __name__ == "__main__":
V, E = map(int, input().split())
for i in range(E):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
s = 0
f = 5
for i in range(V):
visited[i] = False
path[i] = -1
DFSRecursion(s)
printPath(s, f)