[graph coloring problem] detailed optimization

Graph coloring problem

[1]

Given undirected connected graphs, G and m have different colors. These colors are used to color the vertices of graph G, and each vertex has a color. Is there a shading method that makes the 2 vertices of each edge in G have different colors.

[2]

If a graph needs at least m colors to make the two vertices connected by each edge in the graph have different colors, this number m is called the chromatic number of the graph.

Problem solving ideas

[1]Title Link

problem analysis

The first is to give a picture and a fixed color, so that we can judge whether we can dye successfully or have several dyeing schemes;

Problem solving ideas

Backtracking + DFS

  • The i-th node is dyed with dfs(i). When I > N, the dyeing is completed;
  • For each node, it is necessary to enumerate all nodes connected to it to see whether the colors coincide. If the colors coincide, enumerate the next color. If a color does not coincide with the connected node, enumerate the next node (dfs(i+1));
  • After all colors are enumerated, if there are still no qualified ones, go back and enumerate again;
  • If you find it, you don't need to go back, because you only need to judge whether the dyeing can be successful (this should be paid special attention);

Code demonstration

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 110;
int G[maxn][maxn];
int color[maxn];
bool ans;
int n,m,k;
void init(){
//Used for array initialization
    ans = 0;
    memset(G, 0 , sizeof G);
    memset(color, 0 , sizeof color);
}

void dfs(int cur){
    if(cur > n) {
        ans = 1;
        return;    
    } 
    for(int i=1; i<=m; i++){ 
    //Try to paint cur nodes with each color 
    
        bool flag = 1;
        //Nodes before cur must be colored
        for(int j=1; j<cur; j++){
            if(G[j][cur] == 1 && color[j] == i){
                flag = 0;
                //Not as long as there is a conflict 
                break;
            }
        } 
        //If i color can be painted, consider the next node 
        if(flag){
            color[cur] = i;
            dfs(cur + 1);
            //color[curr]=0;
            //!!! When you need to find the number of schemes, backtracking should be put here to find all schemes!!!;
        } 
        //If the cur node cannot be colored at this step, return to explore other schemes 
        else color[cur] = 0;
        //to flash back;
    }
    
}


int main(){
    while(cin>>n>>k>>m){
        init(); 
        for(int i=1; i<=k; i++){
            int x,y;
            cin>>x>>y;
            G[x][y] = G[y][x] = 1;
        }
        dfs(1);
        cout<<ans<<endl;
    }
    return 0;
}

[2]Topic exercise

problem analysis

Given a graph, let's find out the minimum number of colors needed for complete coloring;

Problem solving ideas

Use backtracking to find out all schemes and record the number of colors;

Code demonstration

#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
/*
  vector<int>Room[M]People in the room
    Traverse before selecting a room each time, which is similar to the coloring problem
    G[110][110]Indicates the relationship between people
	dfs(i,j)
	 Indicates that the number of rooms i need to live in is j; 
	*/
	int G[110][110];
	  int n;
	   int ans;
	vector<int>Room[110];
void dfs(int x,int y){
	if(y>=ans)return;
	//prune
	if(x>n){
		ans=min(ans,y);
	//	cout<<"y "<<y<<endl;
		return;
	}
      for(int j=1;j<=y;j++){
      		bool flag=1;
	//Judge whether this room x can live 
	for(int i=0;i<Room[j].size();i++){
		if(G[Room[j][i]][x]){
			flag=0;
			break;
		}
	}
	 if(flag){
	 	//This room is available 
	 	Room[j].push_back(x);
		 dfs(x+1,y);
		 Room[j].pop_back();
	 }
      }
	 	//Open another room for x
		 Room[y+1].push_back(x); 
	 	dfs(x+1,y+1);
	 	Room[y+1].pop_back();
	 	
} 
void init(){
    memset(Room ,  0, sizeof Room);
    memset(G,  0, sizeof G);
    ans = INT_MAX;
}
int main(){
	init(); 
    int m,a,b;
     n=read();
     //Read quickly and update later
     m=read();
     while(m--){
     	a=read();b=read();
     	G[a][b]=G[b][a]=1;
     }
     dfs(1,1);
     cout<<ans;
	return 0;
}

Tags: Algorithm

Posted by peeps on Wed, 25 May 2022 11:38:54 +0300