Đồ thị hai phía là đồ thị có thể tô màu bằng hai màu. Chương trình này kiểm tra tính hai phía bằng thuật toán BFS.
Thuật toán
Bắt đầu
Hàm Bipartite():
1) Gán màu cho đỉnh nguồn.
2) Tô màu các đỉnh kề với màu khác.
3) Tô màu các đỉnh kề của đỉnh kề với màu đầu tiên.
4) Tiếp tục gán màu sao cho thỏa mãn bài toán tô màu k=2.
5) Nếu tìm thấy đỉnh kề cùng màu với đỉnh hiện tại -> không phải hai phía.
Kết thúc
Ví dụ
#include <iostream>
#include <queue>
#define V 5
using namespace std;
bool Bipartite(int G[][V], int s) {
int colorA[V];
for (int i = 0; i < V; ++i)
colorA[i] = -1;
colorA[s] = 1; // màu đỉnh nguồn
queue<int> q;
q.push(s);
while (!q.empty()) {
int w = q.front(); q.pop();
for (int v = 0; v < V; ++v) {
if (G[w][v] && colorA[v] == -1) {
colorA[v] = 1 - colorA[w]; // màu xen kẽ
q.push(v);
}
else if (G[w][v] && colorA[v] == colorA[w])
return false;
}
}
return true;
}
int main() {
int G[][V] = {{0, 1, 0, 0},
{1, 0, 0, 0},
{0, 0, 0, 1},
{1, 0, 1, 0}};
if (Bipartite(G, 0))
cout << "The Graph is Bipartite" << endl;
else
cout << "The Graph is Not Bipartite" << endl;
return 0;
}
Kết quả
The Graph is Bipartite