BFS
Bài học 10 trên 14 trong khóa học Đồ thị, chuỗi cấu trúc dữ liệu #9 của Coddy.
Các thử thách tiếp theo được thiết kế để sử dụng lớp Graph mà bạn vừa tạo.
Mỗi thử thách cung cấp cho bạn một tệp graph bị khóa (tệp Graph cuối cùng từ chương trước) và một tệp solution mới để bạn viết một hàm (function) sử dụng Graph.
Thuật toán đầu tiên của chúng ta: Tìm kiếm theo chiều rộng. Bắt đầu từ một đỉnh, BFS lần lượt thăm tất cả các đỉnh có thể đi đến theo từng lớp: đầu tiên là đỉnh bắt đầu, tiếp theo là mọi đỉnh cách một cạnh, rồi đến mọi đỉnh cách hai cạnh, cứ thế tiếp tục. Cách triển khai kinh điển dùng hàng đợi: thêm đỉnh bắt đầu vào hàng đợi, sau đó liên tục lấy một đỉnh ra, ghi nhận đỉnh đó là đã thăm và thêm mọi đỉnh kề chưa được thăm vào hàng đợi.
Vì danh sách các đỉnh kề không có thứ tự cố định, hai lần chạy BFS đúng có thể tạo ra thứ tự duyệt khác nhau. Để đáp án trong thử thách này luôn có kết quả xác định, hãy sắp xếp các đỉnh kề của mỗi đỉnh theo thứ tự tăng dần trước khi thêm chúng vào hàng đợi.
Thử thách
DễViết một hàm (function) bfs nhận một mảng số nguyên 2D adjacency (mỗi hàng là một cạnh [u, v]) và một số nguyên start, rồi trả về thứ tự duyệt BFS bắt đầu từ start dưới dạng danh sách số nguyên.
Dựng đồ thị: với mỗi [u, v] trong adjacency, gọi g.addEdge(u, v). Sau đó duyệt BFS từ start bằng hàng đợi. Khi xử lý các đỉnh kề, hãy sắp xếp chúng theo thứ tự tăng dần để đầu ra luôn xác định.
Bạn phải dùng lớp Graph (được cung cấp trong graph), không dùng các kiểu dựng sẵn của ngôn ngữ (map, set) để biểu diễn danh sách kề. Dữ liệu phụ trợ cho thuật toán (tập hợp các đỉnh đã thăm, hàng đợi) có thể dùng các kiểu trong thư viện chuẩn.
Tự làm thử
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start;
if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
int out[MAX_VERTICES];
int outn = bfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}
Tất cả bài học trong Đồ thị, chuỗi cấu trúc dữ liệu #9
Tự luyện tập: Trình biên dịch C online