首页 > 代码库 > 欧拉回路&Fleury算法&实现

欧拉回路&Fleury算法&实现

基本知识

欧拉回路:图G,若存在一条路,经过G中每条边有且仅有一次,称这条路为欧拉路,如果存在一条回路经过G每条边有且仅有一次,

称这条回路为欧拉回路。具有欧拉回路的图成为欧拉图。

判断欧拉路是否存在的方法

有向图:图连通,有一个顶点出度大入度1,有一个顶点入度大出度1,其余都是出度=入度。

无向图:图连通,只有两个顶点是奇数度,其余都是偶数度的。

判断欧拉回路是否存在的方法

有向图:图连通,所有的顶点出度=入度。

无向图:图连通,所有顶点都是偶数度。

程序实现一般是如下过程:

1.利用并查集判断图是否连通,即判断p[i] < 0的个数,如果大于1,说明不连通。

2.根据出度入度个数,判断是否满足要求。

3.利用dfs输出路径。

考虑一个比较有意思的问题,单词连接问题。

样例

考虑一个比较有意思的问题,单词连接问题。

给出n个单词,如果一个单词的尾和另一个单词的头字符相等,那么可以相连,问这n个单词是否可以排成一列。

这个显然可以使用欧拉路问题进行解决。考虑每一个单词的第一个字母入度加1,每一个单词的最后一个字母出度加1,然后每一个单词都相当于一条有向边,这样就可以利用这些信息进行是否联通的判断,比较高效的策略是使用并查集进行判断。

实现代码如下:

#include <iostream>
#include <assert.h>
#include <string>
using namespace std;

const int maxv = 27;
int in[maxv];
int out[maxv];
int p[maxv];
int rankk[maxv];
int used[maxv];
void init()
{
   for(int i=0;i<maxv;i++)
   {
      p[i] = i;
      in[i] = 0;
      out[i]=0;
      rankk[i] =1;
   }
}
int find(int a)
{
    if(p[a]==a)
      return p[a];
    p[a] = find(p[a]);
    return p[a];
}

bool unions(int a,int b)
{
    int pa = find(a),pb = find(b);
    if(pa==pb)
      return false;
    if(rankk[pa]>rankk[pb])
    {
        p[pb]=pa;
        rankk[pa]+=rankk[pb];
    }
    else 
    {
        p[pa] = pb;
        rankk[pb]+=rankk[pa];
    }
    return true;
}
int main(int argc,char* argv[])
{
    init();
    int wordCount = 0;
    cin>>wordCount;
    string word;
    while(wordCount>0)
    {
       cin>>word;
       int len = word.size();
       in[word[0]-'a']++;
       out[word[len-1]-'a']++;
       used[word[0]-'a'] = 1;
       used[word[len-1]-'a'] = 1;
       unions(word[0]-'a',word[len-1]-'a');
       wordCount--;        
    }
    int scc = 0;
    for(int i=0;i<maxv;i++)
    {
        if(used[i]&&p[i]==i)
        {
             scc++;
             //break;
        }
    }
    cout<<scc<<endl;
    assert(scc<=1);
    if(scc>1)
    {
       cout<<"scc is greater than 1 so it is not ok exit"<<endl;
       return -1;
    }
    int a=0,b=0;
    for(int i=0;i<maxv;i++)
    {
       if(!used[i])
          continue;
       cout<<'a'+i<<" "<<in[i]<<" "<<out[i]<<endl;
       if(in[i]==out[i])
         continue;
       if(in[i]-out[i]==1)
          a++;
       else if(in[i]-out[i]==-1)
          b++;
       else
      { 
           cout<<"not ok,exit"<<endl;
           return -1;
       }
    }
    if((a==1&&b==1)||a+b==0)
      cout<<"OK"<<endl;
    return 0;
}

Fleury算法

对于有向图和无向图都可以使用Fleury算法累实现寻找欧拉回路问题。下面介绍一下Fleury算法的思路。

Fleury算法:
   任取v0V(G),令P0=v0

Pi=v0e1v1e2ei vi已经行遍,按下面方法从中选取ei+1

aei+1vi相关联;

b)除非无别的边可供行遍,否则ei+1不应该为Gi=G-{e1,e2, , ei}中的桥(所谓桥是一条删除后使连通图不再连通的边);

c)当(b)不能再进行时,算法停止。

可以证明,当算法停止时所得的简单回路Wm=v0e1v1e2.emvm(vm=v0)G中的一条欧拉回路,复杂度为O(e*e)


//
//  Eular.h
//  HelloWorld
//
//  Created by jackqiu on 15-1-5.
//  Copyright (c) 2015年 jackqiu. All rights reserved.
//

#ifndef HelloWorld_Eular_h
#define HelloWorld_Eular_h
class Eular
{
private:
#define SIZE 1000
    int graph[SIZE][SIZE];
    int stack[SIZE+10];
    int top;//the
    int size;
    /**
     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)。
     */
    void DFS(int x,int t)
    {
        stack[++top] = x;
        int brige = 0,i;
        for(i=t;i<size;i++)
        {
            if(graph[x][i])
            {
                graph[x][i] = graph[i][x] = 0;
                brige = 1;
                DFS(i,0);
                break;
            }
        }
        if(brige==0)//没有边的话就往后退
        {
            int beforeX = stack[--top];//相当于先pop,然后取栈顶的元素
            graph[beforeX][x] = graph[x][beforeX] = 1;//回复刚刚的数据,返回的上一个节点
            if(top== size)
            {
                stack[++top] = x;
            }
            else
            {
                top--;
                DFS(beforeX,x+1);//visit the next node of x
            }
        }
    }
public:
    Eular()
    {
        
    }
    void eular()
    {
        cout<<"please input the size:";
        cin>>size;
        cout<<"input the edge for example 1 2  (-1 -1) to exit"<<endl;
        int a,b;
        cin>>a>>b;
        graph[a][b] = graph[b][a] = 1;
        while(a!=-1&&b!=-1)
        {
            cin>>a>>b;
            graph[a][b] = graph[b][a] = 1;
        }
        top = 0;
        DFS(0,0);
        for(;top>0;top--)
        {
            cout<<stack[top]<<" ";
        }
        cout<<endl;
    }
};

#endif






欧拉回路&Fleury算法&实现