图论-欧拉图-欧拉回路-Euler-Fluery-Hierholzer-逐步插入回路法-DFS详解-并查集

欧拉图性质：

1.无向连通图G是欧拉图，当且仅当G不含奇数度结点(G的所有结点度数为偶数)；

2.无向连通图G含有欧拉通路，当且仅当G有零个或两个奇数度的结点；

3.有向连通图D是欧拉图，当且仅当该图为连通图且D中每个结点的入度=出度；

4.有向连通图D含有欧拉通路，当且仅当该图为连通图且D中除两个结点外，其余每个结点的入度=出度，且此两点满足deg－(u)－deg+(v)=±1。（起始点s的入度=出度-1，结束点t的出度=入度-1 或两个点的入度=出度）；

对于欧拉图问题，有如下解决问题的方法：

1.Eular算法（欧拉算法），欧拉问题最标准的算法。

2.Fluery算法（佛罗莱算法），欧拉问题最广泛的算法

3.Hierholzer (希霍尔泽算法应该是这么翻译）又叫逐步插入回路法，高效的算法。

4.DFS算法，暴力无脑解题算法，虽然Fluery，Euler也是递归实现。这个我看看又看了看，确实跟Euler没区别，跟Hierholzer也没区别

5.并查集算法，网络流解混合图的时候可以使用。https://blog.csdn.net/liyanfeng1996/article/details/52767039

以上是网上的各种说法的总结，也就是只有这3种做法，暴力的搜索（1，3，4）

1.对于第一种方法只要有欧拉路径或者欧拉回路，就可以使用，应该是可以用于无向图的，不过使用前需要判断节点的度，是否存在，复杂度有点高，也不用避免隔什么的感觉跟DFS很像，简单的题暴力就完事了。

就是暴力，能走就走，不能走就不走，然后从小号到最大号遍历，也就保证了路径的序号为字典序最小的情况。

模板：

int g[510][510];

stack<int> s;

int d[510];

void euler(int u)

{

    for(int v=1; v<=500; v++)

    {

        if(g[u][v])

        {

            g[u][v]--;

            g[v][u]--;

            euler(v);

            s.push(v);

        }

    }

}

int main()

{

    int u,v;

    int n;

    cin>>n>>m;// 点，边

    for(int i=1; i<=m; i++)

    {

        cin>>u>>v;

        g[u][v]++;

        g[v][u]++;

        d[u]++;

        d[v]++;

    }

    int flag=1;

    int cnt=0;

    for(int i=n; i>=1; i--)

        if(d[i]%2)

        {

            flag=i;

            cnt++;

        }

    if(cnt>2)

    {

        cout<<"No Euler"<<endl;

        return 0;

    }

    euler(flag);

    s.push(flag);

    while(!s.empty())

    {

        cout<<s.top()<<endl;

        s.pop();

    }

}



void fleury(int s){

	bool flag;

	st.push(s);

	while(!st.empty()){

		flag = 0;

		for(int i = 1; i <= n; i++){

			if(edge[st.top()][i] > 0){

				flag = 1; break;

			}

		}

		if(flag){

			int x = st.top();

			st.pop();

			dfs(x);

		}

		else{

			printf("%d ",st.top());

			st.pop();

		}

	}

巴特西

图论-欧拉图-欧拉回路-Euler-Fluery-Hierholzer-逐步插入回路法-DFS详解-并查集

最新文章

热门文章