给定无向连通图G和m种颜色，要求用这些颜色给定点着色要求，每个顶点颜色和相邻顶点不相同。
算法思想：依次对每个点尝试着色，如果颜色重复就换下一个颜色。
#include<iostream> #include<vector> using namespace std; //给定无向连通图G和m种颜色，要求用这些颜色给定点着色要求，每个顶点颜色和相邻顶点不相同。 vector<vector<int>> c(4, vector<int>(4, 0));//图 vector<int> color(4,0);//第i个顶点的颜色 //判断相邻顶点颜色是否重复 bool same(vector<vector<int>> c, int v, vector<int> color) { for (int i = 0; i < c[0].size(); i++) { if (c[v][i] == 1) { if (color[v] == color[i]) { return true; } } } return false; } //算法思想：依次对每个点尝试着色，如果颜色重复就换下一个颜色 void dfs(int k,vector<vector<int>> c, vector<int> color, int m) {//第k个顶点，总共m种颜色，color为染色结果，c为邻接表 if (k==4) { for (auto it : color) { cout << it << " "; } cout << endl; } else { for (int j = 1; j <= m; j++) { color[k]=j; if (!same(c,k,color)) { dfs(k + 1, c, color, m); } } } } int main() { c[0][1] = 1; c[1][0] = 1; c[1][2] = 1; c[2][1] = 1; c[2][3] = 1; c[3][2] = 1; c[3][0] = 1; c[0][3] = 1;//对边进行初始化 dfs(0, c, color, 5); //for (auto it : color) { // cout << it << " "; //} }
给定无向连通图G，要求每个顶点颜色和相邻顶点不相同，求最少要用多少种颜色。
算法思想：每次尝试n种颜色，去着色，1<n<顶点个数，如果能给所有顶点上色则输出n。
#include<iostream> #include<vector> using namespace std; //给定无向连通图G和m种颜色，要求用这些颜色给定点着色要求，每个顶点颜色和相邻顶点不相同。 vector<vector<int>> c(4, vector<int>(4, 0));//图 vector<int> color(4,0);//第i个顶点的颜色 //判断相邻顶点颜色是否重复 bool same(vector<vector<int>> c, int v, vector<int> color) { for (int i = 0; i < c[0].size(); i++) { if (c[v][i] == 1) { if (color[v] == color[i]) { return true; } } } return false; } bool solved = false; //算法思想：依次对每个点尝试着色，如果颜色重复就换下一个颜色 void dfs(int k,vector<vector<int>> c, vector<int> color, int m) {//第k个顶点，总共m种颜色，color为染色结果，c为邻接表 if (k==4) { //for (auto it : color) { // cout << it << " "; //} //cout << endl; solved = true; } else { for (int j = 1; j <= m; j++) { color[k]=j; if (!same(c,k,color)) { dfs(k + 1, c, color, m); } } } } int main() { c[0][1] = 1; c[1][0] = 1; c[1][2] = 1; c[2][1] = 1; c[2][3] = 1; c[3][2] = 1; c[3][0] = 1; c[0][3] = 1;//对边进行初始化 for (int i = 1; i < 5; i++) { dfs(0, c, color, i); if (solved) { cout << i << endl; break; } } }
