В более простых терминах граф называется Bipartite, если никакие две вершины в графе не имеют одинакового цвета, где количество цветов допускается только two.
Приведенный выше граф можно назвать Bipartite graph,
Пояснение:
Пусть два допустимых цвета — красный и синий.
Если мы окрасим узел 0 цветом red, то его соседний узел 1 может быть окрашен blue, а 3 может быть окрашен blue.
Поскольку оба узла 3 и 1 имеют смежные узлы 2 и 2 может быть окрашен цветом red.
Следовательно, никакие два соседних узла не имеют одинакового цвета.
Следовательно, приведенный выше граф называется Bipartite графом.
Примечание: Граф можно раскрасить двумя цветами, если он имеет четный цикл (т.е. четное количество узлов, образующих цикл), но это невозможно для графа с нечетным циклом (когда нечетное количество узлов образует цикл).
Решение: Используя простой алгоритм Breadth-first Algorithm.
Помните, что мы используем 0 и 1 как два разных цвета
class Solution {
public boolean isBipartite(int[][] graph) {
int visited[] = new int[graph.length];
int color[] = new int[graph.length];
for(int i =0;i<graph.length;i++){
// using for loop for all components of the graph.
if(visited[i]==0){
visited[i] =1;
color[i] =0;
if(!isPossible(i,visited,color,graph)) return false;
}
}
return true;
}
public boolean isPossible(int node, int[] visited, int color[], int graph[][]){
Queue<Integer> q = new LinkedList<>();
q.add(node);
while(!q.isEmpty()){
Integer n = q.remove();
for(int it: graph[n]){
if(visited[it]==0){
visited[it] = 1;
if(color[n]==0) color[it] = 1;
else color[it] =0;
q.add(it);
}
else if(color[it]==color[n]){
return false;
}
}
}
return true;
}
}
Мы можем удалить посещаемый массив и сократить количество строк кода, как показано ниже
class Solution {
public boolean isBipartite(int[][] graph) {
int color[] = new int[graph.length];
Arrays.fill(color,-1);
for(int i =0;i<graph.length;i++){
if(color[i]==-1){// color ==-1 means that i has not been visited
color[i] =0;// initially color it with 0
if(!isPossible(i,color,graph)) return false;
}
}
return true;
}
public boolean isPossible(int node,int color[], int graph[][]){
Queue<Integer> q = new LinkedList<>();
q.add(node);
while(!q.isEmpty()){
Integer n = q.remove();
for(int it: graph[n]){
if(color[it] ==-1){
color[it] = 1-color[n]; // so if n's color was 0 , `it` color will be 1 , else 0
q.add(it);
}
else if(color[it]==color[n]){
return false;
}
}
}
return true;
}
}
Решение: Использование Depth-First Search
class Solution {
// using depth first search for checking bipartite graph
public boolean isBipartite(int[][] graph) {
int color[] = new int[graph.length];
Arrays.fill(color,-1);
for(int i =0;i<graph.length;i++){
if(color[i]==-1){
color[i] = 1;
if(!isPossible(i,color,graph)) return false;
}
}
return true;
}
public boolean isPossible(int n, int[] color,int[][] graph){
for(int node : graph[n]){
if(color[node]==-1){
color[node] = 1-color[n];
if(!isPossible(node,color,graph)) return false;
}
else if (color[node] ==color[n]) return false;
}
return true;
}
}