图着色

《数据结构》课程设计 中南民族大学计算机科学学院 专业：计算机科学与技术 学号： 姓名 ：Hades - 1 -

图的着色问题 一、 目的 利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C++语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。

二、 需求分析 1、问题描述

给定无向连通图G=(V, E)，求图G的最小着色数k，使得用k种颜色对G中的顶点着色，可使任意两个相邻顶点着色不同。

2、基本功能 功能一：为了程序的灵活性，可以让程序从磁盘文件中读取图的信息。 功能二：对建好的图进行着色。

3.输入输出 输入：从磁盘文件读入图的顶点连接信息。 输出：在屏幕上输出读取到的，图的顶点间连接信息，方便对照，同时输出所需颜色总数和着色方案。 三、 概要设计

1、设计思路：

先从磁盘文件中读取已有图的顶点连接信息，然后建立邻接表存储邻边。之后各顶点按照相邻顶点颜色不同的原则，用一种颜色给尽可能多的顶点涂色，直到所有的顶点都涂色。

2、数据结构设计： 因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构选用邻接表，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶点相邻接，如果用邻接矩阵会浪费很多的存储空间，所以我选择的邻接表来存储，存储结构如下： 《数据结构》课程设计 中南民族大学计算机科学学院 专业：计算机科学与技术 学号： 姓名 ：Hades - 2 -

typedef struct Side { int data; struct Side *next; }Side;

typedef struct Node { int color; struct Side *next,*tail; }Node;

3、函数定义如下： 1) Node* Build_Node() 操作结果：返回一个Node类型的邻接表 操作：从内存中获得（文件的路径和）文件名，打开文件后，先读取图的顶点数和边数目。按照顶点数为顶点集申请内存空间。之后依次读取一组数据，建立路径。

2) void DFS(Node *node,int num) 参数：传入邻接表的头指针，开始执行的顶点序号（默认从1号开始） 操作结果：根据全局数组Visited的访问记录，找出深度遍历顺序，结果保存在全局数组Order中 操作：先访问传入的顶点，将Visited中对应序号的单元，值改为1，同时该顶点的序号也顺序记录在Order中。然后在该顶点记录的路径中，按照Visited记录的访问记录查找未被访问的节点序号，然后再次调用本函数，直到所有的点都访问过。

3) int Color(Node *node) 参数：已经建立好的邻接表首地址 操作结果：给邻接表的顶点集Color数据域赋好值，并返回所用最大颜色值 操作：按照Order中记录的深度访问顺序，给顶点涂色。涂色过程：用一个变量赋值为一种颜色，依次与跟当前节点有路径的点的颜色比较，直到变量颜色与跟它有路径的其他顶点颜色都不同时，才将变量的颜色赋值给当前顶点，然后给Order中记录的下一顶点涂色

4) Print_color(Node *node,int color_total) 《数据结构》课程设计 中南民族大学计算机科学学院 专业：计算机科学与技术 学号： 姓名 ：Hades - 3 -

参数：传入已经上好颜色的邻接表和 Color(Node *node) 函数返回的最大颜色数 操作结果：顶点的连接关系和图色方案输出到屏幕 四 详细设计

#include #include #define length 40 //定义文件名长度 int Bian=0,Vertex=0,*Visited=NULL,*Order=NULL,count=0; // 定义用到的全局变量 typedef struct Side { int data; struct Side *next; }Side;

typedef struct Node { int color; struct Side *next,*tail; }Node;

//********************* 建邻接表 ****************** Node* Build_Node() { FILE *fp;

char FileName[length]; int dot1=0,dot2=0,i=1; Node *node=NULL; Side *NewSide=NULL; printf("请输入文件名（可包含路径）: "); gets(FileName); 《数据结构》课程设计 中南民族大学计算机科学学院 专业：计算机科学与技术 学号： 姓名 ：Hades - 4 -

if( (fp=fopen(FileName,"r"))==NULL ) { puts("文件打开失败！！"); exit(1); }

fscanf(fp,"%d%*c%d",&Vertex,&Bian); //输入顶点和边的数目 node=(Node*)malloc((Vertex+1)*sizeof(Node) ); // 申请空间 for(i=1;i<=Vertex;i++) // 初始化指针 { node[i].color=0; node[i].next=NULL; node[i].tail=NULL; }

while(!feof(fp)) { fscanf(fp,"%d%*c%d",&dot1,&dot2);

NewSide=(Side*)malloc(sizeof(Side)); //为新增节点申请空间 NewSide->next=NULL; //初始化指针 NewSide->data=dot2; //给新节点记录邻接顶点序号 if(node[dot1].next==NULL) //如果是第一次添加邻接边 { node[dot1].next=NewSide; //将相应序号的顶点与它的邻接边 建立链 node[dot1].tail=NewSide; //tail指向下一个新增节点的位置 } else { node[dot1].tail->next=NewSide; //将新增节点插入 node[dot1].tail=NewSide; //tail始终指向末尾 }

NewSide=(Side*)malloc(sizeof(Side)); // 给这条边的另一个顶点 建立邻接信息 NewSide->next=NULL; NewSide->data=dot1; 《数据结构》课程设计 中南民族大学计算机科学学院 专业：计算机科学与技术 学号： 姓名 ：Hades - 5 -

if(node[dot2].next==NULL) { node[dot2].next=NewSide; node[dot2].tail=NewSide; continue; }

node[dot2].tail->next=NewSide; node[dot2].tail=NewSide; }

printf("\n\n\t\t文件读取成功！！ 任意键返回..."); getch(); return node; }

//******************* 深度遍历顶点 ************************* void DFS(Node *node,int num) // num 表示要访问的节点序号 { int n=0;

count++; Order[count]=num; //以前未被访问，在此处被访问 Visited[num]=1; //改变对应的标志为已经访问

node[num].tail=node[num].next; while(node[num].tail!=NULL) //在该顶点的邻边寻找 未被访问的点 { n=node[num].tail->data;

if(Visited[n]==0) //找到之后，进行递归 DFS(node,node[num].tail->data); else node[num].tail=node[num].tail->next; } } 《数据结构》课程设计 中南民族大学计算机科学学院 专业：计算机科学与技术 学号： 姓名 ：Hades - 6 -

//****************** 给图染色 ******************** int Color(Node *node) //传入图的邻接表 和 图顶点数 { Side *check=NULL;

int i=1,j,color=1,Max_color=0; for(;i<=Vertex;i++) { j=Order[i]; //按 深度遍历的结果来上色 for(color=1;;color++) { check=node[j].next; //开始处与复位功能

while(check!=NULL) //判断当前颜色是否可用 {

if(color == node[check->data].color) // 判断当前颜色与邻边是否相同 { break; } check=check->next; //颜色不相同，则继续往下比较，直到比完所有相连的节点都不相等 }

if( check==NULL ) //如果当前颜色与邻边都不同，则记录该颜色 { node[j].color = color; Max_color= (color > Max_color)? color: Max_color;//记录所用颜色总数 break; } } } return Max_color; }

//************* 打印涂色方案 ***********