Joyce' Blog
0%

算法大作业笔记（一）

发表于 更新于

前期准备

参考网上代码，自己和自己之间为0，不算相连，需要修改—>主要原因是有这一句：if (edges[i][j] && vertexes[j].color == nowcol)

结构体：关于边的信息，保存在bool型的二维数组里；只定义顶点结构。顶点的信息有：行、列、颜色；行和列换成序号吧，更普遍一些。自己到自己，算相连吗……先，算上，不行再改。

目前connectSudo()已经能正确地返回Sudo的顶点连接信息了。接下来，开始读取顶点的信息吧。嗯，现在getVertex(int n, int m)可以读取需要预着色的点了，无颜色的点色号为-1，返回顶点的数组。getEdges(int n,int x)读取边的信息，有n个顶点x条边，注意输入的是x条边，但矩阵应是对称矩阵，有2x个位置要改变。返回bool型二维数组。接下来，需要准备一些图形的数据了。输入顶点数n，预着色点数m，边数x，颜色总数colornum，两个文件存放数据：

  1. 顶点的信息：m行，每行有两个整数，分别是顶点编号和颜色
  2. 边的信息：x行，每一行分别是两个点的序号，表示这两点相连

算法设计

贪心算法

贪心原则：把一个颜色用到不再能用了为止。

扫描所有未着色的顶点集，对其中的每个顶点，确定是否与已着新颜色的任何顶点都不相邻。若不相邻，则着色。

WelchPowell文件里的代码为什么在着色之前要将顶点按照度数递减的次序排序呢？

目前代码对graph1中的数据进行了测试，无误。graph1中存的是17条边的信息。主要代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
void printVertex(vertex* ver,int n)
{
	for (int i = 0; i < n; i++)
		cout << ver[i].index << " " << ver[i].color << "\n";
}

//构造顶点信息,预着色
vertex* getVertexes(int n, int m)
{
	vertex* vertexes = new vertex[n];
	for (int i = 0; i < n; i++)
	{//n为顶点个数，m为已着色的顶点数
		vertexes[i].index = i;
		vertexes[i].color = -1;//-1表示未着色
	}
	int tmp1 = 0, tmp2 = -1;//需要着色的顶点序号和色号
	for (int i = 0; i < m; i++)
	{
		cin >> tmp1 >> tmp2;
		vertexes[tmp1].color = tmp2;
	}
	return vertexes;
}
//构造边的信息
bool** getEdges(int n,int x)
{
	ifstream read;
	read.open("graph1.txt");
	bool** edges = new bool*[n];
	for (int i = 0; i < n; i++)
		edges[i] = new bool[n];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			edges[i][j] = 0;
	int tmp1 = 0, tmp2 = 0;
	for (int i = 0; i < x; i++)
	{
		read >> tmp1 >> tmp2;
		edges[tmp1][tmp2] = 1;
		edges[tmp2][tmp1] = 1;
	}
	read.close();
	return edges;
}
//使用贪心算法为图着色
void colorGraph(int n,int m,int x,int colornum)
{//n为顶点个数，m为预着色的点的个数,x为边的条数，colornum为颜色数
	vertex* vertexes = getVertexes(n,m);
	bool** edges = getEdges(n, x);
	int notcolor = n - m;//未着色的点的个数
	int nowcol = 0;
	while (notcolor){
		for (int i = 0; i < n; ++i){
			if (vertexes[i].color == -1){// 当前顶点未着色
				bool flag = 1;
				for (int j = 0; j < n; ++j) {
					if (edges[i][j] && vertexes[j].color == nowcol){
						flag = 0;
						break;
					}
				}
				if (flag) { vertexes[i].color = nowcol; --notcolor; }
			}
		}
		++nowcol;
	}
	cout << nowcol << "\n";
	printVertex(vertexes, n);
}
void testSudo()
{
	//connectSudo();
	printSudoVertex(getVertexes(81,9));
}
int main()
{
	colorGraph(8,0,17,4);
	system("pause");
	return 0;
}

测试数据

无预着色：

graph1.txt(8个点，0个预着色点，17条边，4个颜色)

graph2.txt(7个点，0个预着色，12条边，4个颜色)

graph3.txt(4个点，0个预着色，5条边，4个颜色)

graph4.txt(6个点，0个预着色，7条边，2个颜色)

（以上数据测试无误，撒花~~~）
预着色：

graph5.txt(6个点，3个预着色，6条边，2个颜色)

color5.txt

graph6.txt(7个点，2个预着色，12条边，7个颜色)

color6.txt

哦豁，graph6出问题了，去debug吧 .-_-.

嗯，还好，输入数据的问题，不是程序的问题，数据已修正。

（以上数据测试无误，撒花~~~）

Sudo

需要先对connectSudo()做一些修改，edge[i][i]应该为false。

然后，现在，先去准备一些Sudo(注意顶点下标和色号都是从0开始的噢！)

这里的测试大概会出问题了，因为贪心算法目光短浅（贪心算法不足以解决所有的数独问题，因为我们没有考虑到每一个位置可能填上的所有数字，而只是贪心地填上当前满足条件的数字，所以之后的其他空格就不一定有数可填了），准备好……

好了，果然，用了11种颜色。纪念一下我失败的代码，下一篇里该做修改了~_~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include<bits/stdc++.h>
struct vertex{
	int index,color;
};
using namespace std;
void printSudoEdges(bool** edges, int n)
{
	ofstream write;
	write.open("sudoConnection.txt");
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			write << edges[i][j] << " ";
		write << "\n";
	}
	write.close();
}
void printSudoVertex(vertex* ver)
{
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
			cout <<setw(4)<< ver[9 * i + j].color << " ";
		cout << "\n";
	}
}
//构造数独的边
bool** connectSudo()
{
	int n = 81;//数独有81个顶点
	bool** edges = new bool*[81];
	for (int i = 0; i < 81; i++)
		edges[i] = new bool[81];
	for (int i = 0; i < 81; i++)
		for (int j = 0; j < 81; j++)
			edges[i][j] = 0;
	//同行同列相连
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			int cur_index = i * 9 + j;
			for (int k = j+1; k < 9; k++)
			{
				edges[cur_index][i * 9 + k] = 1;//行相连
				edges[i * 9 + k][cur_index] = 1;
			}
			for (int k = i+1; k < 9; k++)
			{
				edges[cur_index][j + k * 9] = 1;//列相连
				edges[j + k * 9][cur_index] = 1;
			}

		}
	}
	//同宫相连
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			for (int k = 0; k < 3; k++)
			{
				int cur_index = 9 * i + 3 * j + k;
				for (int p = j+1; p < 3; p++)
				{
					//同宫同列
					edges[cur_index][9 * i + 3 * p + k] = 1;
					edges[9 * i + 3 * p + k][cur_index] = 1;
				}
				for (int q = k+1; q < 3; q++)
				{
					//同宫同行
					edges[cur_index][9 * i + 3 * j + q] = 1;
					edges[cur_index][9 * i + 3 * j + q] = 1;
				}
			}
		}
	}

	printSudoEdges(edges, 81);
	return edges;
}
void printVertex(vertex* ver,int n)
{
	for (int i = 0; i < n; i++)
		cout << ver[i].index << " " << ver[i].color << "\n";
}

//构造顶点信息,预着色
vertex* getVertexes(int n, int m, const char* filename)
{

	vertex* vertexes = new vertex[n];
	for (int i = 0; i < n; i++)
	{//n为顶点个数，m为已着色的顶点数
		vertexes[i].index = i;
		vertexes[i].color = -1;//-1表示未着色
	}
	int tmp1 = 0, tmp2 = -1;//需要着色的顶点序号和色号
	if (m > 0)
	{
		ifstream read;
		read.open(filename);
		for (int i = 0; i < m; i++)
		{
			read >> tmp1 >> tmp2;
			vertexes[tmp1].color = tmp2;
		}
		read.close();
	}
	return vertexes;
}
//构造边的信息
bool** getEdges(int n,int x,const char* filename)
{
	ifstream read;
	read.open(filename);
	bool** edges = new bool*[n];
	for (int i = 0; i < n; i++)
		edges[i] = new bool[n];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			edges[i][j] = 0;
	int tmp1 = 0, tmp2 = 0;
	for (int i = 0; i < x; i++)
	{
		read >> tmp1 >> tmp2;
		edges[tmp1][tmp2] = 1;
		edges[tmp2][tmp1] = 1;
	}
	read.close();
	return edges;
}
//使用贪心算法为图着色
void colorGraph(int n,int m,int colornum, vertex* vertexes, bool** edges)
{
	int notcolor = n - m;//未着色的点的个数
	int nowcol = 0;
	while (notcolor){
		for (int i = 0; i < n; ++i){
			if (vertexes[i].color == -1){// 当前顶点未着色
				bool flag = 1;
				for (int j = 0; j < n; ++j) {
					if (edges[i][j] && vertexes[j].color == nowcol){
						flag = 0;
						break;
					}
				}
				if (flag) { vertexes[i].color = nowcol; --notcolor; }
			}
		}
		++nowcol;
	}
	if (colornum < nowcol)
	{
		cout << "Failed" << "\n";
		return;
	}
	cout << nowcol << "\n";
	printVertex(vertexes, n);
}
void testSudo()
{
	//connectSudo();
	//printSudoVertex(getVertexes(81,30,"sudoColor1.txt"));
	colorGraph(81, 30, 9, getVertexes(81, 30, "sudoColor1.txt"), connectSudo());
}
void testGraph(int n, int m, int x, int colornum, const char* colorfile, const char* graphfile)
{
	//n为顶点个数，m为预着色的点的个数,x为边的条数，colornum为颜色数
	vertex* vertexes = getVertexes(n, m, colorfile);
	bool** edges = getEdges(n, x, graphfile);
	colorGraph(n,m,colornum,vertexes, edges);
}
int main()
{
	//testGraph(7,2,12,7,"graph6.txt","color6.txt");
	testSudo();
	system("pause");
	return 0;
}