弗 罗 莱 （ Fleury） 算 法 ,求 欧 拉 （ Euler） 通 路 /回 路 算法及分析 2009-09-20 17:11:54 阅读807 评论0字号：大中小 1、基本概念： （1）定义 欧拉通路(欧拉迹)—通过图中每条边一次且仅一次，并且过每一顶点的通路。 欧拉回路(欧拉闭迹)—通过图中每条边一次且仅一次，并且过每一顶点的回路。 欧拉图—存在欧拉回路的图。欧拉图就是从一顶出发每条边恰通过一次又能回到出发顶点的那种图，即不重复的行遍所有的边再回到出发点。 通路和回路－称 v ie1e2… env j 为一条从 v i 到 v j 且长度为 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）算法思想－解决欧拉回路 Fleu ry 算法： 任取 v 0∈V(G)，令 P0=v 0； 设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 语言描述 void DFS(Graph &G,SqStack &S,int x,int t) { k=0;//一个标志,来标记当前访问的节点是否还有邻接边可供访问 Push(S,x); //将本次遍历边所经由的点入栈 for(i=t;i0) { k=1; G[i][x]=0; G[x][...
