弗洛莱(Fleury)算法求欧拉通路，欧拉回路（哥尼斯堡七桥问题） |
您所在的位置：网站首页 › 欧拉算法 › 弗洛莱(Fleury)算法求欧拉通路，欧拉回路（哥尼斯堡七桥问题） |
弗洛莱(Fleury)算法求欧拉通路，欧拉回路（哥尼斯堡七桥问题）
|
引入：
在18世纪，东普鲁士哥尼斯堡城内有一条大河，河中有两个小岛。全城被大河分割成四块陆地，河上架有七座桥，把四块陆地联系起来(如图)。当时许多市民都在思索一个问题:一个散步者能否从某一陆地出发，不重复地经过每座桥一次，最后回到原来的出发地。 此乃哥尼斯堡七桥问题！ 数学家欧拉证明了该问题无解，并由此创建了欧拉图，欧拉回路的相关概念，形成了一些重要定理。 欧拉图：通过图中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路。 通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。 具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。 有相关定理： 1.无向图G是欧拉图当且仅当G是连通图且没有奇度顶点 2.无向图G是半欧拉图当且仅当G是连通图且恰有两个奇度顶点 3.有向图D是欧拉图当且仅当D强连通且每个顶点入度等于出度 4.有向图D是欧拉图当且仅当D强连通且恰有两个奇度顶点V1,V2（V1:入度-出度=1，V2:出度-入度=1）其余的顶点出度等于入度 5.G是非平凡的欧拉图当且仅当G是连通的且是若干个边不重的圈的并 定理1，2就可以说明为什么哥尼斯堡七桥问题无解了。 求欧拉回路的算法有两种：插入回路法和弗洛莱算法。弗洛莱算法反映在代码上十分简洁，这里来总结一下 算法的基本思想是：能不走桥就不走桥 算法描述：输入一个图G（首先判断是欧拉图或者半欧拉图） 1.任取顶点v0，令P0=v0，i=0； 2.设Pi=v0->e1->v1->e2…->ei->vi 若在有E(G)-{e1,e2…ei}没有与vi关联的边，则计算停止，否则再从E(G)-{e1,e2…ei)中取一条边ei+1满足： (1) ei+1与vi相关联 (2) ei+1不应该为G-{e1,e2,…,ei}中的桥（即在去掉之前走过的边后的图上，再去掉该边会使图不再连通） 设ei+1=(vi,vi+1)将其加入Pi得到Pi+1 3.i++，重复第二步 若一个图是欧拉图，当计算停止时必然能得到一条欧拉回路。 代码实现：注释已经写得比较清楚了，上代码： #include #include //description:this is a template for Algorithm-Fleury const int MAXN = 100; //define the maximun // struct Stack{ int StackTop; int Node[MAXN]; }; //define a Stack container // Stack s;//a stack int Matrix[MAXN][MAXN];//Matrix for Graph int VertexNum;//Count Vertex; // void DFS(int x) { s.StackTop++; s.Node[s.StackTop]=x;//initialize for(int i=0;i0) { Matrix[x][i]=0; Matrix[i][x]=0; DFS(i);//*dfs recursion* break;//cut branch } } return; } //use DFS to search the graph // void Fleury(int Start) { s.StackTop=0; s.Node[s.StackTop]=Start; while(s.StackTop>=0) { bool IsBridge=true; for(int i=0;i0) { IsBridge=false; break; } } if(IsBridge==true) { std::cout |
这四个顶点ABCD全部都是奇数度顶点【本文地址】
今日新闻 |
推荐新闻 |