1468587
Tìm kiếm theo chiều rộng
https://vi.wikipedia.org/wiki?curid=1468587
Title: Tìm kiếm theo chiều rộng
Có thể dùng thuật toán tìm kiếm theo chiều rộng để kiểm tra xem một đồ thị có phải đồ thị hai phía hay không, bằng cách tìm kiếm từ một đỉnh bất kì và gán nhãn chẵn lẻ cho các đỉnh được quan sát. Nghĩa là, gán nhãn 0 cho đỉnh gốc, 1 cho tất cả các đỉnh kề đỉnh gốc, 0 cho tất cả các đỉnh kề với một đỉnh kề đỉnh gốc, và tiếp tục như vậy. Nếu ở một bước nào đó, có hai đỉnh kề nhau có cùng nhãn, thì đồ thị không là hai phía. Nếu quá trình tìm kiếm kết thúc mà điều này không xảy ra thì đồ thị là hai phía.