Giao diện
Duyệt đồ thị BFS & DFS
🎯 Mục tiêu
Luyện tập BFS và DFS trên danh sách kề, tìm thành phần liên thông, phát hiện chu trình và kiểm tra đồ thị hai phía.
Mô tả bài tập
Cài đặt BFS, DFS và áp dụng vào các bài toán: tìm thành phần liên thông, phát hiện chu trình, kiểm tra bipartite.
Yêu cầu
Bài 1: BFS và DFS trên danh sách kề
Cài đặt BFS và DFS trả về thứ tự các đỉnh được thăm.
python
from collections import deque
def bfs(graph: dict[int, list[int]], start: int) -> list[int]:
# TODO: Cài đặt BFS
pass
def dfs(graph: dict[int, list[int]], start: int) -> list[int]:
# TODO: Cài đặt DFS
pass
graph = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}
print(bfs(graph, 0)) # [0, 1, 2, 3]
print(dfs(graph, 0)) # [0, 2, 3, 1]Bài 2: Tìm thành phần liên thông
Đếm số thành phần liên thông trong đồ thị vô hướng có n đỉnh.
python
def count_components(n: int, edges: list[tuple[int, int]]) -> int:
# TODO: Cài đặt
pass
assert count_components(5, [(0,1), (1,2), (3,4)]) == 2
assert count_components(4, []) == 4Bài 3: Phát hiện chu trình
Kiểm tra xem đồ thị vô hướng có chứa chu trình hay không.
python
def has_cycle(n: int, edges: list[tuple[int, int]]) -> bool:
# TODO: Cài đặt bằng DFS
pass
assert has_cycle(4, [(0,1), (1,2), (2,0)]) == True
assert has_cycle(3, [(0,1), (1,2)]) == FalseBài 4: Kiểm tra đồ thị hai phía (Bipartite)
Kiểm tra xem đồ thị có thể tô bằng 2 màu sao cho không có hai đỉnh kề nhau cùng màu.
python
def is_bipartite(n: int, edges: list[tuple[int, int]]) -> bool:
# TODO: Cài đặt bằng BFS tô màu
pass
assert is_bipartite(4, [(0,1), (1,2), (2,3)]) == True
assert is_bipartite(3, [(0,1), (1,2), (2,0)]) == FalsePhân tích độ phức tạp
| Bài | Time | Space |
|---|---|---|
| 1 - BFS/DFS | O(V + E) | O(V) |
| 2 - Thành phần liên thông | O(V + E) | O(V + E) |
| 3 - Phát hiện chu trình | O(V + E) | O(V + E) |
| 4 - Bipartite check | O(V + E) | O(V + E) |
Gợi ý
Gợi ý Bài 2
Duyệt tất cả đỉnh từ 0 đến n-1. Mỗi khi gặp đỉnh chưa thăm, chạy BFS/DFS từ đỉnh đó và tăng bộ đếm thành phần.
Gợi ý Bài 3
Dùng DFS và theo dõi đỉnh cha (parent). Nếu gặp đỉnh đã thăm mà không phải đỉnh cha → có chu trình.
Gợi ý Bài 4
Dùng BFS và gán màu 0/1 cho mỗi đỉnh. Khi duyệt hàng xóm, nếu chưa tô thì tô màu ngược lại; nếu đã tô cùng màu → không phải bipartite.
Lời giải tham khảo
Xem lời giải
python
from collections import deque
def bfs(graph: dict[int, list[int]], start: int) -> list[int]:
visited, queue, order = {start}, deque([start]), []
while queue:
node = queue.popleft()
order.append(node)
for nb in graph[node]:
if nb not in visited: visited.add(nb); queue.append(nb)
return order
def has_cycle(n: int, edges: list[tuple[int, int]]) -> bool:
graph = {i: [] for i in range(n)}
for u, v in edges: graph[u].append(v); graph[v].append(u)
visited = set()
def dfs_check(node, parent):
visited.add(node)
for nb in graph[node]:
if nb not in visited:
if dfs_check(nb, node): return True
elif nb != parent: return True
return False
for i in range(n):
if i not in visited and dfs_check(i, -1): return True
return False
def is_bipartite(n: int, edges: list[tuple[int, int]]) -> bool:
graph = {i: [] for i in range(n)}
for u, v in edges: graph[u].append(v); graph[v].append(u)
color = [-1] * n
for i in range(n):
if color[i] == -1:
queue = deque([i])
color[i] = 0
while queue:
node = queue.popleft()
for nb in graph[node]:
if color[nb] == -1: color[nb] = 1 - color[node]; queue.append(nb)
elif color[nb] == color[node]: return False
return True