Một đồ thị được cho là đồ thị lưỡng phân, khi các đỉnh của đồ thị đó có thể được chia thành hai tập độc lập sao cho mọi cạnh trong đồ thị đều bắt đầu từ tập đầu tiên và kết thúc bằng tập hợp thứ hai, hoặc bắt đầu từ tập hợp thứ hai, được kết nối với tập hợp đầu tiên, nói cách khác, chúng ta có thể nói rằng không thể tìm thấy cạnh nào trong cùng một tập hợp.
Có thể kiểm tra đồ thị hai bên bằng cách sử dụng màu đỉnh. Khi một đỉnh nằm trong cùng một tập hợp, nó có cùng màu, đối với một tập hợp khác, màu đó sẽ thay đổi.
Đầu vào và Đầu ra
Input: The adjacency matrix. 0 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 Output: The graph is bipartite.
Thuật toán
isBipartite(source)
Đầu vào - Đỉnh nguồn.
Outpu t :Đúng khi biểu đồ là lưỡng phân.
Begin define an empty queue qu, and a color list coloArray initially any node is not colored with any color color the source vertex as color red add source in the qu when qu is not empty, do remove item from the qu and take in u if there is any self-loop, then return false for all vertices v, which is connected with u, do if v has no color, then if colorArray[u] = red, then colorArray[v] := blue else if colorArray[u] = blue, then colorArray[v] := red add v into the queue if colorArray[v] = colorArray[u], then return false done done return true End
Ví dụ
#include<iostream>
#include<string>
#include<queue>
#define NODE 6
using namespace std;
/*int graph[NODE][NODE] = {
{0, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0},
{1, 0, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 1},
{0, 1, 0, 1, 0, 1},
{0, 0, 1, 1, 1, 0}
}; */
int graph[NODE][NODE] = {
{0, 1, 0, 0, 0, 1},
{1, 0, 1, 0, 0, 0},
{0, 1, 0, 1, 0, 0},
{0, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 1},
{1, 0, 0, 0, 1, 0}
};
bool isBipartite(int source) {
queue<int> qu;
string colorArray[NODE];
for(int i = 0; i< NODE; i++)
colorArray[i] = "No Color"; //initially no color is set for all vertices
colorArray[source] = "Red"; //assign red with the source vertex
qu.push(source); //add source into the queue.
while(!qu.empty()) {
int u = qu.front();
qu.pop();
if(graph[u][u] == 1) //there is a self loop
return false;
for(int v = 0; v < NODE; v++) {
if(graph[u][v] != 0 && colorArray[v] == "No Color") {
if(colorArray[u] == "Red") //assign adjacent list with alternate color
colorArray[v] = "Blue";
else if(colorArray[u] == "Blue")
colorArray[v] = "Red";
qu.push(v); //new adjacent node added to queue
} else if(graph[u][v] != 0 && colorArray[v] == colorArray[u]) {
return false; //when u and adjacent are of same color.
}
}
}
return true;
}
int main() {
bool check;
check = isBipartite(0);
if(check)
cout << "The graph is bipartite." << endl;
else
cout << "The graph is not bipartite." << endl;
} Đầu ra
The graph is bipartite.