基于实现韦尔奇·鲍威尔法对图进行着色

编程内容及要求：

编写程序，实现输入图G，基于韦尔奇·鲍威尔法对图G的结点进行着色，输出对应的一个正常着色。

正常着色输出格式示例(设图G的结点为v1, v2, v3，颜色用1, 2, 3等数字代表):

------------------

v1:1,v2:2,v3:3

------------------

韦尔奇·鲍威尔法：

1)  将图 G 中的结点按度数递减的次序进行排列(相同度数的结点的排列随意)。 

2)  用第一种颜色，对第一点着色，并按排列次序对与前面结点不相邻的每一点着同样的颜色。 

3)  用第二种颜色对尚未着色的点重复第2 步, 直到所有的点都着上颜色为止。 

程序设计简要描述：

首先输入一个结点数v，在int型二维数组matrix（初始化为0）里输入图的邻接矩阵，再调用getdegree()函数，在这个函数里面将矩阵每一行的列数据相加得到每个结点的度数并存储于一个二维数组a中，a有两行并初始化为0，第一行用来存储所有结点的度数，第二行准备用来存储相应结点的着色。接着调用sort()函数，用一个一维数组as（初始化为0），运用循环将a数组的第一行复制到as数组中，运用冒泡排序的思想依次获取结点度数从大到小的数组下标并存储于一维数组ascend中，在main()函数中借助ascend中的下标使用韦尔奇·鲍威尔法进行着色，将着色数据存储于a数组的第二行。最后运用文件操作将结果输出到graph.txt中。

输出的字符文件graph.txt内容（粘贴）：

------------------

v1:1,v2:3,v3:2,v4:2,v5:1,v6:3,v7:3,v8:2

------------------

#include <iostream> #include <fstream> using namespace std; #define Maxsize 100 int v, color = 1; int matrix[Maxsize][Maxsize]; int a[2][Maxsize] = { 0 }; int ascend[Maxsize] = { 0 }; void getdegree(); void sort(); int main() {cout << "请输入要着色的图G结点数：" << endl;cin >> v;cout << "请输入图G的邻接矩阵：" << endl;for (int i = 0; i < v; i++)for (int j = 0; j < v; j++)cin >> matrix[i][j];getdegree();sort();//借助ascend中的下标使用韦尔奇·鲍威尔法进行着色，将着色数据存储于a数组的第二行for (int i = 0; i < v; i++){if (a[1][ascend[i]] == 0){a[1][ascend[i]] = color;for (int j = 0; j < v; j++){if (matrix[ascend[i]][j] == 0){if (a[1][j] == 0)a[1][j] = color;}}color++;}}//运用文件操作将结果输出到graph.txt中ofstream ofs;ofs.open("graph.txt", ios::out);ofs << "------------------" << endl;for (int i = 0; i < v; i++){ofs << "v" << i + 1 << ":" << a[1][i];if (i != v - 1)ofs << ",";}ofs << endl << "------------------" << endl;ofs.close();return 0; } //将矩阵每一行的列数据相加得到每个结点的度数并存储于一个二维数组a中 //a有两行并初始化为0，第一行用来存储所有结点的度数，第二行准备用来存储相应结点的着色。 void getdegree() {for (int i = 0; i < v; i++)for (int j = 0; j < v; j++)a[0][i] += matrix[i][j]; } //获取结点度数从大到小的数组下标并存储于一维数组ascend中 void sort() {int flag = 0;int as[Maxsize] = { 0 };for (int i = 0; i < v; i++)as[i] = a[0][i];for (int i = 0; i < v; i++){int temp = 0;for (int j = 0; j < v; j++){if (as[j] > temp){temp = as[j];flag = j;}}ascend[i] = flag;as[flag] = 0;} }

总结

以上是生活随笔为你收集整理的基于实现韦尔奇·鲍威尔法对图进行着色的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。