Tìm đường đi ngắn nhất trên đồ thị bằng BFS

Mục tiêu kiến thức

• Xây dựng danh sách kề (Adjacency List) từ danh sách cạnh của đồ thị vô hướng.
• Thuật toán Tìm kiếm theo chiều rộng (BFS) đảm bảo tìm đường đi có số cạnh ít nhất trên đồ thị không trọng số.
• Kỹ thuật truy vết đường đi bằng mảng / từ điển parent.

Mô tả bài toán

Hệ thống mạng truyền thông giữa các máy chủ AI tại AI Empire Academy gồm n nút mạng được đánh số từ 0 đến n - 1. Các liên kết hai chiều giữa các máy chủ được biểu diễn dưới dạng danh sách cạnh edges.

Hãy viết hàm shortest_path_unweighted(n: int, edges: list[tuple[int, int]], start: int, target: int) -> list[int] | None tìm đường đi ngắn nhất (chứa ít cạnh nhất) từ nút start đến nút target.

Quy tắc:

• Trả về danh sách thứ tự các nút trên đường đi bắt đầu từ start và kết thúc tại target (ví dụ: [start, v1, v2, target]).
• Nếu start == target, trả về [start].
• Nếu có nhiều đường đi có cùng độ dài ngắn nhất, ưu tiên chọn đỉnh kề có chỉ số nhỏ hơn trước (duyệt danh sách kề theo thứ tự tăng dần).
• Nếu không có đường đi nào giữa hai nút, trả về None.

Ràng buộc

• 1 ≤ n ≤ 10⁴.
• 0 ≤ len(edges) ≤ 5 · 10⁴.
• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.