弗洛莱(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就可以说明为什么哥尼斯堡七桥问题无解了。

在这里插入图片描述

这四个顶点ABCD全部都是奇数度顶点

Fleury算法

求欧拉回路的算法有两种：插入回路法和弗洛莱算法。弗洛莱算法反映在代码上十分简洁，这里来总结一下

算法的基本思想是：能不走桥就不走桥

算法描述：

输入一个图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<iostream>
#include<string.h>
//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;i<VertexNum;i++)//try an unvisited edge,then delete it
 {
  if(Matrix[x][i]>0)
  {
   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;i<VertexNum;i++)//judge if the edge is a bridge
  {
   if(Matrix[s.Node[s.StackTop]][i]>0)
   {
    IsBridge=false;
    break;
   }
  }
  if(IsBridge==true)
  {
   std::cout<<s.Node[s.StackTop]+1<<"-";
   s.StackTop--;
  }
  else
  {
   s.StackTop--;
   DFS(s.Node[s.StackTop+1]);//Next vertex;
  }
 }
 std::cout<<"end"<<std::endl;
}
//Fleury Algorithm
//
int main()
{
 memset(Matrix,0,sizeof(Matrix));//Initialize the Matrix
 //
 int Ecnt,Estart,Eend;//Edge index
 int Degree;//Vertex's Degree
 int OddDegreeCnt;
 int Pstart;//EulerPath's Start
 std::cout<<"input :VertexAmount EdgeAmount"<<std::endl;
 std::cin>>VertexNum>>Ecnt;
 //
 std::cout<<"Add an Edge: start end "<<std::endl;
 for(int i=0;i<Ecnt;i++)
 {
  std::cin>>Estart>>Eend;
  Matrix[Estart-1][Eend-1]++;
  Matrix[Eend-1][Estart-1]++;
 }//Add edge
 //
 OddDegreeCnt=0;
 Pstart=0;
 for(int i=0;i<VertexNum;i++)
 {
  Degree=0;
  for(int j=0;j<VertexNum;j++)
  {
   Degree+=Matrix[i][j];
  }
  if(Degree%2==1)
  {
   OddDegreeCnt++;
   Pstart=i;
  }
 }//Count OddDegreeVertex
 //
 if(OddDegreeCnt==0)
 {
  std::cout<<"Eluer Circuit:"<<std::endl;
  Fleury(Pstart);
 }
 else if(OddDegreeCnt==2)
 {
  std::cout<<"Eluer Path:"<<std::endl;
  Fleury(Pstart);
 }
 else
 {
  std::cout<<"Isn't Eluer Graph"<<std::endl;
 }
 return 0;
}