проверьте, является ли график двудольным или нет
Я изучаю графики, после того как я закончил писать код о BFS, у меня возник вопрос: как я могу улучшить свой код, чтобы он также проверял, является ли этот график двудольным или нет? используя ту же функцию.
Я хочу покрасить узлы, которые посещает код, вот так
int color; // — 1 (неокрашенный для непосещенного узла), 1 (красный для родителя), 0 (синий для детей)
кто-нибудь может мне помочь с этим :)?
struct node {
int child_count;
int child[max];
int color;
};
void BFS(node*G[], int s){
int w, v;
queue <int> q;
bool visited[max];
for (int i = 0; i < s; i++){
visited[i] = false;
}
for (int i = 0; i < s; i++){
if (!visited[i])
q.push(i);
while (!q.empty())
{
v = q.front();
if (!visited[v])
{
visited[v] = true;
for (int i = 0; i < G[v]->child_count; i++)
{
w = G[v]->child[i];
q.push(w);
}
}
q.pop();
}
}
}
Решение
Код в Java
void bfs(int adjacency_matrix[][], int source){
Queue<Integer> queue = new LinkedList<>();
int numNodes = adjacency_matrix[source].length - 1;
boolean [] visited = new boolean[numNodes + 1];
int element;
HashMap<Integer, Integer> colors = new HashMap<>();
visited[source] = true; // set source vertex/node as visited so we start from it
queue.add(source); // add source to the queue
colors.put(source, 0); // assign color 0
while(!queue.isEmpty()){
element = queue.remove(); // remove head node.. this is parent
for(int i = 0; i < numNodes; i++){
if(adjacency_matrix[element][i] == 1 && Objects.equals(colors.get(i), colors.get(element))){ // same set with different number
System.out.println("not bipartite here "+i+" and "+element); // this will give duplicate.. use set
}
if(adjacency_matrix[element][i] == 1 && visited[i] == false){
queue.add(i); // child
visited[i] = true;
colors.put(i, 1 - colors.get(element)); // this will make it alternate
}
}
}
System.out.println();
}
Другие решения
Вот код на C ++.
#include <iostream>
#include <vector>
#include <list>
#include <queue>
struct Edge{
int source;
int destination;
};
void addEdge(std::vector<Edge> edges, std::vector<std::list<int>> &adjList){
for(int i = 0; i < edges.size(); i++){
int source = edges[i].source;
int destination = edges[i].destination;
adjList[source].push_back(destination);
// And because it's an undirected grapgh
adjList[destination].push_back(source);
}
}
void printGraph(int nodes, std::vector<std::list<int>> adjList){
for(int i = 0; i < nodes; i++){
std::cout << i << ":";
std::list<int>::iterator it;
for(it = adjList[i].begin(); it != adjList[i].end(); it++)
std::cout << *it << "->";
std::cout << "NULL\n";
}
}
bool check_bipartite(int nodes, int start,
std::vector<std::list<int>> adjList){
std::vector<bool> visited(nodes, false);
std::queue<int> q;
visited[start] = true;
// -1 means no colour is assigned. 0 means red and 1 means blue
std::vector<int> colours(nodes, -1);
q.push(start);
// Assign it red colour
colours[start] = 0;
while(!q.empty()){
int a = q.front();
q.pop();
std::list<int>::iterator it;
for(it = adjList[a].begin(); it != adjList[a].end(); it++){
if(!visited[*it]){
q.push(*it);
// It won't have any colour assigned yet
// Assign a colour opposite to the parent
colours[*it] = ((colours[a] == 0) ? 1 : 0);
std::cout << "Colour of " << *it << " = " << colours[*it] << std::endl;
// Mark it as visited
visited[*it] = true;
}
// If this vertex has already been visited
// Check if the colour of the parent is different from this vertix
else if(visited[*it]){
if(colours[a] == colours[*it])
return false;
}
}
}
return true;
}
int main(){
// Un-directed graph
// Vertex 0 is an un-connected node
int nodes1 = 10;
std::vector<Edge> edges1 = {
{1, 2},
{2, 3},
{2, 8},
// Add this edge to make it non-bipartite
//{2, 4},
{3, 4},
{4, 6},
{5, 7},
{5, 9},
{8, 9}
};
// Create an adjacency graph
std::vector<std::list<int>> adjList(nodes1);
// Add all nodes
addEdge(edges1, adjList);
// Print the adjacency graph
printGraph(nodes1, adjList);
if(check_bipartite(nodes1, 1, adjList))
std::cout << "It's a bipartite grapgh.\n";
else
std::cout << "It's NOT a bipartite graph.\n";
return 0;
}