logo资料库

欧拉回路的实验报告.doc

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.13M 资料格式：doc 举报 版权申诉
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
资料共6页，全文预览结束
    欧拉（Euler）通路/回路 1、基本概念： （1）定义 欧拉通路 (欧拉迹)—通过图中每条边一次且仅一次，并且过每一顶点的通路。 欧拉回路 (欧拉闭迹)—通过图中每条边一次且仅一次，并且过每一顶点的回路。 欧拉图—存在欧拉回路的图。欧拉图就是从一顶出发每条边恰通过一次又能回到出发顶点的 那种图，即不重复的行遍所有的边再回到出发点。 通路和回路－称 vie1e2…envj 为一条从 vi 到 vj 且长度为 n 的通路，其中长度是指通路中边的 条数．称起点和终点相同的通路为一条回路。 简单图－不含平行边和自回路的图。 混合图－既有有向边，也有无向边的图 平凡图－仅有一个结点的图 完全图－有 n 个结点的且每对结点都有边相连的无向简单图，称为无向完全图；有 n 个结点 的且每对结点之间都有两条方向相反的边相连的有向简单图为有向完全图。 （2）欧拉图的特征： 无向图 a）G 有欧拉通路的充分必要条件为：G 连通，G 中只有两个奇度顶点(它们分别是欧拉通路 的两个端点)。 b）G 有欧拉回路(G 为欧拉图)：G 连通，G 中均为偶度顶点。 有向图 a）D 有欧拉通路：D 连通，除两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶 点中，一个顶点的入度比出度大 1，另一个顶点的入度比出度小 1。 b）D 有欧拉回路(D 为欧拉图)：D 连通，D 中所有顶点的入度等于出度。一个有向图是欧拉 图，当且仅当该图所有顶点度数都是 0。 2、弗罗莱（Fleury）算法思想－解决欧拉回路 Fleury 算法： 任取 v0∈V(G)，令 P0=v0； 设 Pi=v0e1v1e2…ei vi 已经行遍，按下面方法从中选取 ei+1： （a）ei+1 与 vi 相关联； （b）除非无别的边可供行遍，否则 ei+1 不应该为 Gi=G-{e1,e2, …, ei}中的桥（所谓桥 是一条删除后使连通图不再连通的边）； （c）当（b）不能再进行时，算法停止。 可以证明,当算法停止时所得的简单回路 Wm=v0e1v1e2….emvm(vm=v0)为 G 中的一条 欧拉回路，复杂度为 O(e*e)。 3、欧拉算法 C 语言描述 如下为算法的图示动态过程：
    4、欧拉算法的 C 实现 #include "SqStack.h" //堆栈的常见操作 #include "Queue.h"//队列的常见操作 typedef int Graph[200][200]; int v,e; void DFS(Graph &G,SqStack &S,int x,int t) { int k=0,i,m,a; Push(S,x); for(i=t;i0) { k=1; G[i][x]=0; //删除此边 G[x][i]=0; DFS(G,S,i,0); break; }//if,for if(k==0) { Pop(S); GetTop(S,m); G[x][m]=1; G[m][x]=1; a=x+1; if(StackLength(S)!=e) {
    Pop(S); DFS(G,S,m,a); }//if else Push(S,x); }//if }//DFS int BFSTest(Graph G) { int a[200],x,i,k=0; LinkQueue Q; InitQueue(Q); EnQueue(Q,0); for(i=0;i0) if(a[i]!=1) { a[i]=1; EnQueue(Q,i); }//if }//while for(i=0;i
    InitStack(S); DFS(G,S,x,0); printf("该图的一个欧拉回路为："); while(!StackEmpty(S)) { GetTop(S,m); printf("->v%d",m); Pop(S); }//while } void InputM1(Graph &G) { int h,z; printf("Please input 顶点数和边数\n"); scanf("%d",&v); scanf("%d",&e); for(int i=0;i
    sum=0; for(j=0;j
    汉密尔顿图与欧拉图的区别只在于，边与顶点的区别，欧拉图是每边经过一次，汉密尔 顿图是每顶经过一次。
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料