Có phải đồ thị hai phía không
Bài học 14 trên 14 trong khóa học Đồ thị, chuỗi cấu trúc dữ liệu #9 của Coddy.
Một đồ thị là hai phía nếu bạn có thể chia các đỉnh thành hai nhóm sao cho mỗi cạnh nối một đỉnh ở nhóm này với một đỉnh ở nhóm kia. Hãy hình dung hai màu đỏ và xanh dương: mỗi cạnh có một đầu mút màu đỏ và một đầu mút màu xanh dương.
BFS giúp kiểm tra điều này một cách rõ ràng. Bắt đầu từ một đỉnh bất kỳ, tô màu đỏ cho đỉnh đó rồi duyệt ra ngoài. Mỗi đỉnh kề mới sẽ nhận màu đối lập với màu của đỉnh mà ta vừa đi từ đó đến. Nếu ta thấy một cạnh nối hai đỉnh có cùng màu, đồ thị không phải là đồ thị hai phía. Trường hợp điển hình là một chu trình có độ dài lẻ: tam giác 0-1-2-0 buộc đỉnh 0 phải vừa có màu đỏ vừa có màu xanh dương.
Hãy nhớ một điều: nếu đồ thị có nhiều thành phần liên thông, bạn phải bắt đầu tô hai màu mới cho từng thành phần. Cách đơn giản nhất là dùng một vòng lặp duy nhất qua tất cả các đỉnh, bắt đầu BFS mỗi khi gặp một đỉnh chưa được tô màu.
Thử thách
DễViết một hàm isBipartite nhận mảng số nguyên 2 chiều adjacency và mảng số nguyên vertices, rồi trả về true nếu đồ thị là hai phía, nếu không thì trả về false.
Dựng đồ thị bằng cách gọi addVertex cho từng đỉnh, rồi gọi addEdge cho từng cạnh. Sau đó tô hai màu bằng BFS trên từng thành phần liên thông: gán màu 0 cho đỉnh bắt đầu, gán cho mỗi đỉnh kề màu 1 - color[u]. Nếu gặp cạnh mà hai đầu mút đã có cùng màu, hãy trả về false. Nếu không, hãy trả về true.
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 (bản đồ màu, 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;
if (scanf("%d %d", &n, &m) != 2) return 0;
int vertices[MAX_VERTICES];
for (int i = 0; i < n; i++) scanf("%d", &vertices[i]);
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%s\n", isBipartite(adjacency, m, vertices, n) ? "true" : "false");
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