算法分析设计实践——M着色问题
标签：str 输入 std 算法分析 不同的 play tps void 技术
1. 问题
给定无向连通图G=（V,E）和M中不同的角色，用这些颜色为图G的个顶点着色，每个顶点着一种颜色。是否有一种着色算法是G中相邻的两个顶点有不同的颜色？给出所有可能的着色方案；如果不存在，则回答“NO”
2.解析
回溯法
使用回溯法，具体步骤是将cur=1传入dfs（），即从第一个开始涂色。
涂的时候从颜色1开始到m，每当涂上一个色，要用checked（cur）判断第cur个点是否可以涂这个色，不可以的话就不再往下涂了，改试另一个颜色，可以的话就继续。
当cur>n的时候即前n个点都涂完了，然后输出结果并cnt++计数。
3.设计
1 bool check(int c){
2 for(int k=1;k){
3 if(graph[c][k]&&color[c]==color[k]){
4 return false;
5 }
6 }
7 return true;
8 }
9
10 void dfs(int cur){
11 if(cur>n){
12 for(int i=1;i){
13 printf("%d ",color[i]);
14 }
15 cnt++;
16 printf("\n");
17 }else{
18 for(int i=1;i){
19 color[cur]=i;
20 if(check(cur)){
21 dfs(cur+1);
22 }
23 color[cur]=0;
24 }
25 }
26 }
4.完整代码
1 #include 2 #include 3
4 using namespace std;
5
6 int n,m;
7 int a=1,b=1;
8 int cnt=0;
9 int graph[20][20]={0};
10 int color[20]={0};
11
12 bool check(int c){
13 for(int k=1;k){
14 if(graph[c][k]&&color[c]==color[k]){
15 return false;
16 }
17 }
18 return true;
19 }
20
21 void dfs(int cur){
22 if(cur>n){
23 for(int i=1;i){
24 printf("%d ",color[i]);
25 }
26 cnt++;
27 printf("\n");
28 }else{
29 for(int i=1;i){
30 color[cur]=i;
31 if(check(cur)){
32 dfs(cur+1);
33 }
34 color[cur]=0;
35 }
36 }
37 }
38
39 int main()
40 {
41 scanf("%d %d",&n,&m);
42 while(scanf("%d %d",&a,&b)!=EOF&&a!=0&&b!=0){
43 graph[a][b]=1;
44 graph[b][a]=1;
45 }
46 dfs(1);
47 if(cnt > 0)
48 {
49 printf("Total=%d",cnt);
50 }
51 else
52 {
53 printf("NO\n");
54 }
55
56 return 0;
57 }
58 /*
59 样例输入：
60 5 4
61 1 3
62 1 2
63 1 4
64 2 3
65 2 4
66 2 5
67 3 4
68 4 5
69 0 0
70
71 样例输出：
72 1 2 3 4 1
73 1 2 3 4 3
74 1 2 4 3 1
75 1 2 4 3 4
76 1 3 2 4 1
77 1 3 2 4 2
78 1 3 4 2 1
79 1 3 4 2 4
80 1 4 2 3 1
81 1 4 2 3 2
82 1 4 3 2 1
83 1 4 3 2 3
84 2 1 3 4 2
85 2 1 3 4 3
86 2 1 4 3 2
87 2 1 4 3 4
88 2 3 1 4 1
89 2 3 1 4 2
90 2 3 4 1 2
91 2 3 4 1 4
92 2 4 1 3 1
93 2 4 1 3 2
94 2 4 3 1 2
95 2 4 3 1 3
96 3 1 2 4 2
97 3 1 2 4 3
98 3 1 4 2 3
99 3 1 4 2 4
100 3 2 1 4 1
101 3 2 1 4 3
102 3 2 4 1 3
103 3 2 4 1 4
104 3 4 1 2 1
105 3 4 1 2 3
106 3 4 2 1 2
107 3 4 2 1 3
108 4 1 2 3 2
109 4 1 2 3 4
110 4 1 3 2 3
111 4 1 3 2 4
112 4 2 1 3 1
113 4 2 1 3 4
114 4 2 3 1 3
115 4 2 3 1 4
116 4 3 1 2 1
117 4 3 1 2 4
118 4 3 2 1 2
119 4 3 2 1 4
120 Total=48
121
122
123 */
View Code
5.分析
空间复杂度：O（n）
6.源码
https://github.com/BambooCertain/Algorithm.git
算法分析设计实践——M着色问题
标签：str 输入 std 算法分析 不同的 play tps void 技术
原文地址：https://www.cnblogs.com/DreamACMer/p/13034716.html
评论