图着色Word文档格式.docx
- 文档编号:6554512
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:15
- 大小:70.49KB
图着色Word文档格式.docx
《图着色Word文档格式.docx》由会员分享,可在线阅读,更多相关《图着色Word文档格式.docx(15页珍藏版)》请在冰点文库上搜索。
typedefstructNode
intcolor;
structSide*next,*tail;
}Node;
3、函数定义如下:
1)Node*Build_Node()
操作结果:
返回一个Node类型的邻接表
操作:
从内存中获得(文件的路径和)文件名,打开文件后,先读取图的顶点数和边数目。
按照顶点数为顶点集申请内存空间。
之后依次读取一组数据,建立路径。
2)voidDFS(Node*node,intnum)
参数:
传入邻接表的头指针,开始执行的顶点序号(默认从1号开始)
根据全局数组Visited的访问记录,找出深度遍历顺序,结果保存在全局数组Order中
先访问传入的顶点,将Visited中对应序号的单元,值改为1,同时该顶点的序号也顺序记录在Order中。
然后在该顶点记录的路径中,按照Visited记录的访问记录查找未被访问的节点序号,然后再次调用本函数,直到所有的点都访问过。
3)intColor(Node*node)
已经建立好的邻接表首地址
给邻接表的顶点集Color数据域赋好值,并返回所用最大颜色值
按照Order中记录的深度访问顺序,给顶点涂色。
涂色过程:
用一个变量赋值为一种颜色,依次与跟当前节点有路径的点的颜色比较,直到变量颜色与跟它有路径的其他顶点颜色都不同时,才将变量的颜色赋值给当前顶点,然后给Order中记录的下一顶点涂色
4)Print_color(Node*node,intcolor_total)
传入已经上好颜色的邻接表和Color(Node*node)函数返回的最大颜色数
顶点的连接关系和图色方案输出到屏幕
四详细设计
#include<
stdio.h>
stdlib.h>
#definelength40//定义文件名长度
intBian=0,Vertex=0,*Visited=NULL,*Order=NULL,count=0;
//定义用到的全局变量
//*********************建邻接表******************
Node*Build_Node()
FILE*fp;
charFileName[length];
intdot1=0,dot2=0,i=1;
Node*node=NULL;
Side*NewSide=NULL;
printf("
请输入文件名(可包含路径):
"
);
gets(FileName);
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,"
dot1,&
dot2);
NewSide=(Side*)malloc(sizeof(Side));
//为新增节点申请空间
NewSide->
next=NULL;
//初始化指针
data=dot2;
//给新节点记录邻接顶点序号
if(node[dot1].next==NULL)//如果是第一次添加邻接边
{
node[dot1].next=NewSide;
//将相应序号的顶点与它的邻接边建立链
node[dot1].tail=NewSide;
//tail指向下一个新增节点的位置
}
else
node[dot1].tail->
next=NewSide;
//将新增节点插入
//tail始终指向末尾
//给这条边的另一个顶点建立邻接信息
data=dot1;
if(node[dot2].next==NULL)
node[dot2].next=NewSide;
node[dot2].tail=NewSide;
continue;
node[dot2].tail->
node[dot2].tail=NewSide;
\n\n\t\t文件读取成功!
任意键返回..."
getch();
returnnode;
}
//*******************深度遍历顶点*************************
voidDFS(Node*node,intnum)//num表示要访问的节点序号
{
intn=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;
//******************给图染色********************
intColor(Node*node)//传入图的邻接表和图顶点数
Side*check=NULL;
inti=1,j,color=1,Max_color=0;
for(;
i++)
j=Order[i];
//按深度遍历的结果来上色
for(color=1;
;
color++)
{
check=node[j].next;
//开始处与复位功能
while(check!
=NULL)//判断当前颜色是否可用
{
if(color==node[check->
data].color)
//判断当前颜色与邻边是否相同
{break;
check=check->
//颜色不相同,则继续往下比较,直到比完所有相连的节点都不相等
}
if(check==NULL)//如果当前颜色与邻边都不同,则记录该颜色
node[j].color=color;
Max_color=(color>
Max_color)?
color:
Max_color;
//记录所用颜色总数
break;
}
returnMax_color;
//*************打印涂色方案***********
Print_color(Node*node,intcolor_total)
inti=1,j=1;
\n图的连接状况如下:
\n\t\t"
check=node[i].next;
while(check!
=NULL)
printf("
%d==>
%d"
i,check->
check=check->
printf("
\n\t\t"
\n此图需要%d种颜色:
color_total);
=color_total;
{
\n\n\t\t涂颜色%d的点有:
i);
for(j=1;
j<
j++)
if(node[j].color==i)
{printf("
j);
\n\n\t\t\t\t\t\t任意键返回..."
//**************菜单***********************
Menu()
intchoose=-1,i=1,color_count=0;
do{
system("
cls"
\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"
\t\t☆☆\n"
\t\t☆地图着色☆\n"
\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n\n\n\n"
\t\t◇1读取文件\n\n"
\t\t◇2打印着色方案\n\n"
\t\t◇0退出\n"
\n\n\t\t您想:
scanf("
%d"
choose);
if(choose<
0||choose>
2)continue;
switch(choose)
case1:
fflush(stdin);
system("
node=Build_Node();
break;
case2:
Visited=(int*)malloc((Vertex+1)*sizeof(int));
//申请跟顶点对应的“是否访问”的记录数组
Order=(int*)malloc((Vertex+1)*sizeof(int));
//记录访问顺序
for(i=1;
i++){Visited[i]=0;
Order[i]=0;
}
DFS(node,1);
//默认从第一个顶点进行深度遍历
color_count=Color(node);
Print_color(node,color_count);
break;
case0:
printf("
\t\t\t\t"
exit
(1);
}while
(1);
//*******主函数******************
main(){Menu();
五调试分析
1、从文件中读取数据时:
从文件中读取数据时,要常因为文件尾和数据中的空白间隔符(如空格,换行)等把握不准,而导致读取数据失败。
思考:
要学会处理空格和换行,以及缓冲输入输出流中的多余数据。
2、运用指针和malloc函数:
在读取数据,建立链表时,要用到循环,而循环是有时依据指针是否为空,判断到达链表尾。
在申请空间后,忘记初始化结构中的指针,导致死循环,或程序访问出错。
要养成初始化变量的习惯。
六测试结果
1、菜单
运行程序后,出现菜单界面如上图,输入选项序号进行下一步。
2、文件内容:
说明:
文件以坐标的方式保存,第一组由顶点数和边数组成;
其余的按顺序依次输入边,以空白符隔开。
注意:
文件末尾,不能有空白字符。
3、读取文件:
在菜单下选择1后,进入读取文件功能,输入文件名,限50字符,读取成功后将出现上图情形。
4、打印图连接状况和着色方案:
涂色前:
涂色后:
红色:
颜色1绿色:
颜色2紫色:
颜色3
七用户使用说明
使用本程序之前,客户需要自己建立一个图,然后按照图将其顶点数、边数保存在磁盘文件中。
文件数据格式如下方所示。
有了磁盘文件后,运行程序,选择读取文件,从用户指定位置读取,默认读取位置在与本程序同目录下。
之后可按提示进行打印涂色方案。
数据格式:
其余的尽量按顺序依次输入边,数据组之间以空白字符隔开。
八课程设计总结
本次课程设计,涉及到图的邻接顶点的访问和图的遍历。
图的存储结构我选择的是邻接表的形式,在遍历图时是从第一个顶点开始,一次在定点数组中完成所有顶点的遍历,保证了全部的顶点都是可以访问到的。
因为要对地图着色,所以着色是一个动态的过程,可以在遍历的过程中完成对地图的着色,每次访问一个结点,先赋值第一种颜色,如果和它的的邻接点的颜色不重复,则对下个顶点开始着色,否则本顶点的颜色转换到下一种,直到能够完成赋值。
程序编写本身并不难,思路很清晰,就是赋值和比较之间的来回循环。
写程序的时候查阅了着色问题,直到了这个问题是用计算机进行证明的,地图到目前为止还没有出现这个证明的反例;
而且也明白了计算机在现代数学中的重要作用,因为如果没办法归纳证明,那就可以使用计算机进行穷举,只要穷举出来没有反例出现,则可以说明他没有问题。
此次巩固了我对图这种数据结构的认识,掌握了图的建立,图的数据的存取,使我在这块知识上的认识更加巩固了。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 着色