图论作业第三丁点着色

1、络嚼It矣求衣葬Harbin I nstituteof Technology图论作业课程名称：图 论设计题目：顶点着色近似算法院系：软件学院设计者：林晓宇学号：10S137038教师：匡正算法实现 ：/*根据顺序着色法对一个无向图进行顶点着色*近似计算出此图的顶点着色*Author ：*Date ： 2010-9-18*/#include #include using namespace std;const int MAX = 100; / 最大顶点说struct Nodeint isLink; / 用来表示顶点之间是否连接 如果是则值为 1，否则为 0 int color; / 表示此顶点是

2、用何种颜色着色;/ 定义存储图的二维数组struct Node NodeColorMAXMAX;/ 初始化数组且数组是从一开始存储的void Initialization(int N)for(int i = 1 ;i=N;i+)for(int j = 1;j=N;j+)NodeColorij.isLink = 0;NodeColorij.color = 0;/ 计算顶点着色void ComputerColor(int number)int maxcolorMAX;memset(maxcolor,0,sizeof(int)*(number+1);NodeColor11.isLink = 0;No

3、deColor11.color = 1;for(int i = 2 ;i=number;i+)memset(maxcolor,0,sizeof(int)*(number+1); for(int j = 1;ji;j+) if(NodeColorij.isLink !=0) maxcolorNodeColorjj.color = NodeColorjj.color; for(int k =1;k=number;k+)if(maxcolork=0)NodeColorii.color = k; break;int main()int nodeNumber; / 一共有多少个顶点 coutnodeNu

4、mber;Initialization(nodeNumber); / 初始化数组/ 用二维数组来存储图for(int i =1 ;i=nodeNumber;i+)for(int j = 1;jNodeColorij.isLink;int maxcolor =0;ComputerColor(nodeNumber);for(int i =1;imaxcolor)maxcolor = NodeColorii.color;/输出顺序顶点着色的色数coutThis digram noding color is :maxcolore ndl; return 0;说明：输入分两步，第一步输入的是图的顶点个数

5、。第二步输入的是图，输入限制如下格式。A B C D E F GA 0 1 0 1 0 0 0B 1 0 1 0 1 0 1C 0 1 0 1 1 0 0D 1 0 1 0 1 0 1E 0 1 1 1 0 1 0F 0 0 0 0 1 0 1G 0 1 0 1 0 1 0其中1表示的是这两顶点相邻，零表示这两个顶点不想领。 运行如下：提示用户输入顶点数目：输入数字7点回车_E:workC + +The C+ + programming IanguageSequenceColorbinDebugequenceCoIor-.领人以占的数：u 陽输X图：0 10 10 0 010 10 10 1Q 1 0 1 1 0 010 10 10 10 1110 100 0 0 0 10 10 10 10 10.当用户输入图的矩阵后，点击回车输出结果如下图:j E:workC+iThe C+ + programming languageSequenceColorbinDebug