着色问题实验报告书.docx
《着色问题实验报告书.docx》由会员分享，可在线阅读，更多相关《着色问题实验报告书.docx（8页珍藏版）》请在冰点文库上搜索。
着色问题实验报告书
学生课程实验报告书
09级计算机科学与信息技术系
网络工程专业02班
学号：
0930040250姓名：
郭文明
2010-2011学年第二学期
实验项目：
实验三着色问题
实验目的：
本次实习的主要目的在于熟悉队列的基本运算在存储结构上的实现，其中以熟悉各种链表的操作为侧重点。
通过本次实习还可帮助读者复习高级语言的使用方法。
实验内容：
【问题描述】
对于给定的图G，如果存在一种用2种颜色对顶点着色的方案，使得图中任意一条边所连接的2个顶点着有不同颜色，则称图G是可2着色的。
【编程任务】
对于给定的图G，编程计算图G是否可2着色的。
【数据输入】
由文件input.txt给出输入数据。
第1行有2个正整数n和m，表示给定的图G有n个顶点和m条边，顶点编号为1，2，…，n。
接下来的m行中，每行有2个正整数u,v，表示图G的一条边（u,v）。
【结果输出】
将编程计算出的图G的2着色性输出到文件output.txt。
如果图G不是可2着色的，则输出“No”；如果图G是可以2着色的，则输出“Yes”，并输出一种2着色方案。
【输出示例】
输入文件示例
input.txt
87
13
16
28
37
45
56
58
输出文件示例
output.txt
Yes
11001010
【实验程序如下】
#include/*malloc（）等*/
#include/*EOF（=^Z或F6）,NULL*/
#include/*exit（）*/
/*函数结果状态代码*/
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
#defineOVERFLOW-2
#defineMAXQSIZE50/*最大队列长度（对于循环队列，最大队列长度要减1）*/
typedefintQElemType;
typedefintStatus;
typedefstruct
{
QElemType*base;/*初始化的动态分配存储空间*/
intfront;/*头指针,若队列不空,指向队列头元素*/
intrear;/*尾指针,若队列不空,指向队列尾元素的下一个位置*/
}SqQueue;
/*构造一个空队列Q*/
StatusInitQueue（SqQueue&Q）
{
Q.base=（QElemType*）malloc（MAXQSIZE*sizeof（QElemType））;
if（!
Q.base）/*存储分配失败*/
exit（OVERFLOW）;
Q.front=Q.rear=0;
returnOK;
}
/*若队列Q为空队列,则返回TRUE,否则返回FALSE*/
StatusQueueEmpty（SqQueueQ）
{
if（Q.front==Q.rear）/*队列空的标志*/
returnTRUE;
else
returnFALSE;
}
/*插入元素e为Q的新的队尾元素*/
StatusEnQueue（SqQueue&Q,QElemTypee）
{
if（（Q.rear+1）%MAXQSIZE==Q.front）/*队列满*/
returnERROR;
Q.base[Q.rear]=e;
Q.rear=（Q.rear+1）%MAXQSIZE;
returnOK;
}
/*若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR*/
StatusDeQueue（SqQueue&Q,QElemType&e）
{
if（Q.front==Q.rear）/*队列空*/
returnERROR;
e=Q.base[Q.front];
Q.front=（Q.front+1）%MAXQSIZE;
returnOK;
}
intflag（intedges[][20],intfind[],intcolor[],SqQueueQ,intn）
{
intk,x,i,m=1;
for（k=1;k<=n;k++）
{
if（find[k]==1）
continue;
EnQueue（Q,k）;
find[k]=1;
color[k]=1;
while（!
QueueEmpty（Q））
{
DeQueue（Q,x）;
for（i=0;i<=n;i++）
{
if（edges[x][i]==1）
{
if（find[i]==-1）
{
find[i]=1;
EnQueue（Q,i）;
if（color[x]==1）
color[i]=0;
if（color[x]==0）color[i]=1;
}
else
{
if（color[i]==color[x]）
returnm=0;
}
}
}
}
}
returnm;
}
voidmain（）
{
intn,e,i,j,k,m;
SqQueueQ;
InitQueue（Q）;
intedges[20][20];
intfind[20];
intcolor[20];
printf（"请输入结点个数和边的条数（格式：
结点个数边的条数）:
\n"）;//以下部分为建图
scanf（"%d%d",&n,&e）;
for（i=0;i<=n;i++）
for（j=0;j<=n;j++）
edges[i][j]=0;
printf（"请输入边（格式为：
边的左结点边的右结点）：
\n"）;
for（i=1;i<=e;i++）
{
scanf（"%d%d",&j,&k）;
edges[j][k]=1;
edges[k][j]=1;
}//邻接矩阵建立完毕
for（i=1;i<=n;i++）//初始化find数组
{
find[i]=-1;
color[i]=-1;
}
m=flag（edges,find,color,Q,n）;
if（m）
{
printf（"Yes\n"）;
printf（"着色方案如下：
\n"）;
for（i=1;i<=n;i++）
printf（"%d",color[i]）;
printf（"\n"）;
}
else
printf（"No\n"）;
}
【实验输出】
①第一种输出：
②第二种输出：
升级会员 