着色问题实验报告书.docx
- 文档编号:2127677
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:8
- 大小:87.63KB
着色问题实验报告书.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
#include
#include
/*函数结果状态代码*/
#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");
}
【实验输出】
①第一种输出:
②第二种输出:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 着色 问题 实验 报告书
![提示](https://static.bingdoc.com/images/bang_tan.gif)