{
if(d[i]%2!=0)y++;
} 1.23、欧拉回路的判断
判断欧拉回路时根据欧拉定理进行判断，首先要判断是否为连通图，不是连通图就不进 行后面的判断。如果时连通图且图中 M 个顶点的度都为偶数则存在欧拉回路，因此，欧拉 图一笔画的判定与求解就是对输入的无向连通图是度的判定。当连通图中所有顶点的度都为 偶数时，连通图就存在欧拉回路。
scanf("%d",&node[i]);scanf("%d",&node[i+1]); node[i+2]=node[i+1];node[i+3]=node[i]; x=node[i]; d[x]++; x=node[i+1]; d[x]++; i=i+4; } for(i=1;i<=M;i++)//结点度的判断 { if(d[i]%2!=0)y++; } for(i=1;i<=M;i++) { vertex_node[i].vertex=i; vertex_node[i].flag=0; vertex_node[i].nextnode=NULL; } creat_graph(node,2*N); if(dfs(1)<M||(y!=0)) {tu[a]=0;}
连通图采用邻接表存储，，并且输入顶点信息。 输入的数据为无向图的顶点数和边数，顶点数为大于 0 小于 1000 的整数，边数为非负 的整数，还有邻接表中结点的值（起点和终点），都为非负整数。 输入的无向图，可为连通也可不连通，也可输入单个顶点的图，程序会进行判断。 1.2、算法描述 1.2.1、无向图的存储结构和连通图的判定 采用邻接表存储无向图，利用 graph 表示邻接表用来存储无向图，输入结点数 M 和边 数 N，还有邻接表的值（起点和终点），即边的信息。 图的连通性的判断，用到图的深度优先搜索，采用深度优先搜索来遍历无向图中的点的 信息，从图中某个顶点出发首先访问该顶点，然后任选一个该点未访问的邻接点出发，直到 访问完成。计算出深度优先搜索到点的数目，然后与结点数进行比较，如果遍历到的数目小 于结点数，则为非连通图，否则，为连通图。 1.22、无向图结点度的求法 在无向图建立时求图结点的度，当输入结点信息时用数组 d[i]来存储各节点的度然后判 断度得奇偶性 for(i=1;i<=M;i++)//结点度的判断
开始
输入节点数为 0 N
建立无向图的邻接表
N 是连通图
Y Y
N 顶点度都为偶
数 Y
欧拉回路
不是欧拉图
结束
2、main(主函数） 1.4 creat_graph(邻接矩表建立函数）
功能：根据输入的顶点数和边数还有邻接表的值建立无向图的邻接表。 参数含义：数组 vertex_node 为结构体变量，graph 为结构体类型，数组 node[i]存储结 点。 简单的工作过程：从键盘输入顶点数和边数，邻接表的值（起点和终点）；初始化邻接
p=p->nextnode; p->nextnode=newnode; } } 无向图的深度优先搜索，其中 s 是返回搜索道边的数目。定义指针 p，用 flag 标志结点 是都被访问过。S 用来记录访问过的结点的数目。 int dfs(int k) { graph p; vertex_node[k].flag=1; printf("vertex[%d]",k); s++;
利用深度优先遍历的基本操作来实现的欧拉算法求解欧拉回路。算法就是深度优先遍历 连通图，然后求出连通图中各结点的度。 四、系统设计 1.1 设计说明
该程序设计共包括四大模块：主函数模块，邻接表建立模块，连通图判定模块，欧拉回
路求解模块。主函数中调用了其他所有三个模块，连通图的判定模块与欧拉回路解模块都调 用了邻接表建立模块中建立的邻接表，主函数中包含了结点度的计算，以及欧拉回路判断的 输出。函数模块关系如图 1 所示：
欧拉回路的判定
主函数模 块
邻接表建立模 块
连通图判 定模块
（主函数中） 欧拉回路判 断和输出
1、函数模块关系图 1.2 数据结构描述
该程序主要用到图等数据结构，它们的表示和实现如下所示： 图的存储，用的是连接表存储。定义邻接表的结点和指针，数组 node[i]用来存储结点 信息。通过输入边的信息，用邻接表对无向图进行存储。 void creat_graph(int *node,int n) {graph newnode,p;
附 录（程序清单）
#include<stdio.h> #include<stdlib.h> int s=0; struct node { int vertex;
int flag; struct node *nextnode; }; typedef struct node *graph;//结点类型 struct node vertex_node[10]; void creat_graph(int *node,int n)//图的存储 { graph newnode,p;//定义一个新节点及指针 int x,y,i; for(i=0;i<n;i++) { x=node[i*2];//边的起点
p=p->nextnode;//寻找链尾 p->nextnode=newnode;//在链尾处插入新节点 } } int dfs(int k)//连通图判定 { graph p; vertex_node[k].flag=1;//将标志位置 1，证明该节点访问过 s++;
p=vertex_node[k].nextnode;//指针指向下一节点 while(p!=NULL) { if(vertex_node[p->vertex].flag==0)//判断该节点的标志位是否为零
int start,end,i; for(i=0;i<n;i++) { start=node[i*2];
end=node[i*2+1]; newnode=(graph)malloc(sizeof(struct node)); newnode->vertex=end; newnode->nextnode=NULL; p=&(vertex_node[start]); while(p->nextnode!=NULL)
3、输出结果 输入验证单结点的无向图和多结点无向图，以及偶来图和非欧拉图。 程序对测试输入为： 43 121323 输出结果如下图 4：
4、输出结果 输入验证输入无向图为非连通图图，用来判断无向图是否为欧拉图。 程序对测试输入为： 一组：3 3 1 2 1 3 2 3 二组：3 2 1 2 2 3 输出结果如下图 5：
dfs(p->vertex);//继续遍历下一节点 p=p->nextnode; }return s;//返回访问节点数目 } void main() { int node[100],i,a=-1,x,y=0,d[100],N,M; int tu[10];
printf("\t*************************** 欧 拉 回 路 的 判 断 ***************************\t\n");
表；根据输入的起点和终点用 node[i]存储结点信息；这样邻接表就建立完成。 1.5dfs(连通图判定函数)
功能：判断输入的无向图是否为连通图。 参数含义：graph p 为之前建立好的无向图的邻接表。 简单的工作过程：图的深度优先的过程，用到图的深度优先搜索，采用深度优先搜索来 遍历无向图中的点的信息，从图中某个定点出发首先访问该顶点，然后任选一个该点未被访 问的邻接点出发，直到访问完成。计算出深度优先搜索到点的数目，然后与结点数进行比较， 如果遍历到的数目小于结点数，则为非连通图，否则，为连通图。 1.6 欧拉回路求解 功能：求解连通图的欧拉回路并输出。 此过程是在主函数中实现的。简单的工作过程：有欧拉图的定义来判断。如果一个无相 连通图中各结点的度均为偶数，则是偶来回路。根据函数是否为连通图以及各结点的度，来 判断无向图是否存在欧拉回路。若是输出 yes，否则输出 no。 五、测试结果及其分析 程序的测试结果和输出为： 输入为： 一组：1 0 二组：3 2 1 2 1 3 三组：3 3 1 2 1 3 2 3 输出结果如下图 3：
y=node[i*2+1];//边的终点 newnode=(graph)malloc(sizeof(struct node)); newnode->vertex=y;//新节点的内容为边终点处顶点的内容 newnode->nextnode=NULL; p=&(vertex_node[x]);//设置指针位置 while(p->nextnode!=NULL)
while(12){s=0; a++;y=0; for(i=0;i<100;i++) d[i]=0;
printf("输入结点数和边数:"); scanf("%d",&M); if(M==0)break;scanf("%d",&N); if(N!=0) printf("输入边信息:\n"); for(i=0;i<4*N;)//将节点信息存入数组中 {
合肥学院 计算机科学与技术系
课程设计报告
2012 ～2013 学年第 二 学期
课
程
课程设计名称
学生姓名
学
号
专业班级
指导教师
数据结构与算 欧拉回路
计算机科学与技术系 11 级 4 班
2013 年 3 月