Fleury算法-输出欧拉回路

港控/mmm° 2022-09-25 05:28 101阅读 0赞

佛洛莱算法输出欧拉回路。

![20160814170408257][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <set>
    #include <iomanip>
    #include <algorithm>
    #define maxn 10010
    #define INF 0xfffffff
    using namespace std;
    struct Stack
    {
        int top,node[maxn];
    }s;
    int edge[maxn][maxn];//邻接矩阵
    int n;//顶点个数
    void dfs(int x)
    {
        int i;
        ++s.top;
        s.node[s.top]=x;
        for(i=0;i<n;++i)
            if(edge[i][x]>0)
        {
            edge[i][x]=0;//删除该边
            edge[x][i]=0;
            dfs(i);
            break;
        }
    }
    void Fleury(int x)
    {
        int i,b;
        s.top=0;//入栈
        s.node[s.top]=x;
        while(s.top>=0)
        {
            b=0;
            for(i=0;i<n;++i)
                if(edge[s.node[s.top]][i]>0)
            {
                b=1;
                break;
            }
            if(b==0)//如果没有点可以扩展，输出并出栈
            {
                cout<<s.node[s.top]+1<<" ";
                --s.top;
            }
            else
            {
                --s.top;
                dfs(s.node[s.top+1]);//如果有点可以扩展
            }
        }
        cout<<endl;
    }
    int main()
    {
        int i,j;
        int m,s,t;//边数、读入边的起点终点
        int degree,num,start;//每个顶点的度、奇度顶点个数、欧拉回路的起点
        cin>>n>>m;
        memset(edge,0,sizeof(edge));
        for(i=0;i<m;++i)
        {
            cin>>s>>t;
            edge[s-1][t-1]=1;edge[t-1][s-1]=1;
        }
        //如果存在奇度顶点，则从奇度顶点出发，否则从顶点0出发
        num=0;start=0;
        for(i=0;i<n;++i)//判断是否存在欧拉回路
        {
            degree=0;
            for(j=0;j<n;++j)
                degree+=edge[i][j];
            if(degree%2==1)
            {
                start=i;++num;
            }
        }
        if(num==0||num==2) Fleury(start);
        else cout<<"No Euler path"<<endl;
        return 0;
    }
    
    /*
    9 14
    1 2
    1 8
    2 3
    2 8
    2 9
    3 4
    4 5
    4 6
    4 9
    5 6
    6 7
    6 9
    7 8
    8 9
    */

[20160814170408257]: /images/20220718/e591b28c19a6496c9a44128e548555f8.png