A5c41a8925006234101db93792738949
Fleury 算法

1 概念

  在之前文章中介绍了欧拉通路以及欧拉回路是否存在的判断,本篇文章将介绍使用Fleury算法去求解欧拉通路或者欧拉回路。
  欧拉通路:经过图G(v,e)的每条边一次,且仅仅一次的通路称为欧拉通路,也称为欧拉迹。
  欧拉回路:经过图G(v,e)的每条边一次,且仅仅一次的回路称为欧拉回路,也称为欧拉闭迹。
  割点:若无向图G为连通图,若去除某个顶点vi,此时图不再为连通图,则称顶点vi为图G的一个“割点”。
  割边:若无向图G为连通图,若去除某条边ei,此时图不再为连通图,则称边ei为图G的“割边”,也称作“桥”。

例如下图2.1中,顶点v2,v3为图的割点,边e4为图的桥。
图2.1

图2.1

2 算法流程

  (1)任取v0∈V(G),令P0=v0;
  (2)设pi = v0,e1,v1,e2,...ei,vi已经走遍,按下面方法从E(G)-{e1,e2,e3,...,ei}中选取ei+1;
    a:ei+1与vi相关联;
    b:除非没有别的边可以走,否则ei+1不应该为Gi = G-{e1,e2,e3,...,ei}中的桥。
  (3)当步骤(2)不能在进行时,算法停止。

3 实例讲解

例如选择图2.1中所示的图G为例说明使用Fleury算法求解欧拉通路。
(1)选择v0作为出发点,则p0=v0

(2)e1和e3均不为桥,因此可以随意选择,这里我们选择e1边。得到
  p1 = v0,e1,v1

(3)顶点v1出发,只能选择e2边。此时
  p2 = v0,e1,v1,e2,v2

(4)顶点v2出发,e3不为桥,而e4为桥,选择e3边。
  p3 = v0,e1,v1,e2,v2,e3,v0

(5)到达v0后不能再继续前进,算法终止,因此从v0作为出发点不能找到欧拉通路。

top Created with Sketch.