Mình xin trình bày lời giải bài này theo từng bước như sau:

Bước 1: Biểu diễn đồ thị đã cho dưới dạng danh sách đỉnh kề, cụ thể dưới hình sau:

Bước 2: Gọi \(d[i]\) là khoảng cách ngắn nhất từ đỉnh \(i\) đến đỉnh \(s\) với mọi \(i=1,2,...,n\) và giá trị của tất cả \(d[i]\) này ban đầu là vô cùng (cụ thể ở đây ta gán \(d[i]=inf\) với \(inf=10^{18}\))

• Công việc tiếp theo đó là chúng ta đi tính \(d[i]\) thông qua hàm \(BFS()\) như sau:

Mình xin giải thích cụ thể đoạn code trên như sau:

• Step 1: Rõ ràng ta có ngay \(d[s]=0\)

• Step 2: Tiếp theo những đỉnh mà kề với \(s\) thì sẽ được tính theo công thức như sau: \(d[v]=min(d[v],d[s]+1)\) (Với mọi \(v\) kề với \(s\)).

Một điều quan trọng được xem như linh hồn của hàm BFS đó chính là cấu trúc dữ liệu queue (Bạn nào chưa biết có thể lên mạng tìm hiểu, vì nó là một cấu trúc dữ liệu kinh điển và được sử dụng thường xuyên), ở đây mình chỉ đề cập đến hai lệnh phổ biến hàm queue hai dùng đó là:

• \(q.pop()\): Lấy phần tử đầu tiên ra khỏi queue. Ví dụ ban đầu \(q = \left\{4,3,6,7\right\}\). Thì sau khi thực hiện lệnh: \(q.pop(), q = \left\{3,6,7\right\}\)

• \(p=q.front()\): Gán phần tử đầu tiên của queue cho \(p\). Vì dụ \(q\left\{4,7,8\right\}\). Thì \(p = q.front() = 4\)

• Step 3: Ta cần dùng một mảng để đánh dấu những đỉnh đã được duyệt qua, để tránh hàm while lặp vô tận.

Bước 3: Đó là bước in ra. Ở bước này, ta chú ý rằng, sau khi đã tính xong mảng \(d[]\). Ta chỉ cần in ra những đỉnh nào mà có \(d[i]\ne inf\). Nhưng trước đó ta cần xử lý một chút, để in ra đúng theo yêu cầu bài toán, đó là các đỉnh được in ra phải theo thứ tự tăng dần của \(d[i]\) và nếu có hai đỉnh nào cùng \(d[i]\) thì nhãn nào bé hơn sẽ in ra trước.

Do đó ta nên lưu những đỉnh có \(d[i]\ne inf\) vào một vector và sau đó sort lại là xong:

Cụ thể:

Như vậy là bài toán đã được giải quyết xong !

Ps:

• Nếu có gì thắc mắc hoặc sai sót các bạn cứ tự nhiên comment nhé

• Các bạn có thể tham khảo code tại đây