图-欧拉图(欧拉环游/回路、欧拉迹/通路、Hierholzer算法、Fleury算法)

以你之姓@ 2022-12-02 14:00 367阅读 0赞

**目录**

概念

欧拉迹/通路（一笔画）

半欧拉图

环游

欧拉环游/回路

欧拉图

欧拉定理

推论

Hierholzer 算法

作用

内容

时间复杂度

图

代码

截图

Fleury算法

作用

内容

时间复杂度

图

代码

截图

--------------------

# 概念 #

## 欧拉迹/通路（一笔画） ##

通过图中每条边且行遍所有顶点的迹（每条边恰一次的途径），称为欧拉迹（Euler trail）。

## 半欧拉图 ##

具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图，有且仅有两个度数为奇数的结点。

## 环游 ##

图的环游(tour)是指经过图的每条边至少一次的闭途径。

## 欧拉环游/回路 ##

经过每条边恰好一次的环游/回路欧拉环游/回路（Eular tour）。

## 欧拉图 ##

一个图若包含欧拉环游，则称为欧拉图(Euleriangraph)。

## 欧拉定理 ##

一个非空连通图是欧拉图当且仅当它的每个顶点的度数都是偶数。

## 推论 ##

1.  无向连通图 G 是欧拉图，当且仅当 G 不含奇数度结点( G 的所有结点度数为偶数)；
2.  无向连通图 G 含有欧拉通路，当且仅当 G 有零个或两个奇数度的结点；
3.  有向连通图 D 是欧拉图，当且仅当该图 D 中每个结点的入度=出度；
4.  有向连通图 D 含有欧拉通路，当且仅当该图D 中除两个结点外，其余每个结点的入度=出度，且此两点满足 deg-(u)-deg+(v)=±1 。（起始点s的入度=出度-1，结束点t的出度=入度-1 或两个点的入度=出度）；
5.  一个非平凡连通图是欧拉图当且仅当它的每条边属于奇数个环；
6.  如果图G是欧拉图且 H = G-uv，则 H 有奇数个 u,v-迹仅在最后访问 v ；同时，在这一序列的 u,v-迹中，不是路径的迹的条数是偶数。

# Hierholzer 算法 #

## 作用 ##

寻找半欧拉图、欧拉图的欧拉迹、欧拉环游/回路。

## 内容 ##

1.  选择任一顶点为起点（半欧拉图需要选择两个度数为奇数的结点中的一个），遍历所有相邻边。
2.  深度搜索，访问相邻顶点。将经过的边都删除。
3.  如果当前顶点没有相邻边，则将顶点入栈。
4.  栈中的顶点倒序输出，就是从起点出发的欧拉迹、欧拉环游/回路。

为什么需要栈呢？因为存在死胡同（运行过程中先遍历某个点，这个点通过入边遍历后删除入边没有出边了，但是图中还有边没有遍历）

![2020083118505778.PNG][] 存在死胡同c

不使用栈，若a为起点，遍历哪个点就加入某数据结构（例如队列 ），先遍历c。

a加入队列。

遍历ac，c入队列，删除ac,。

遍历ab,b入队列，删除ab。

遍历ba,a入队列，删除ba。

结果为a->c->b->a。但其实应该是a->b->a->c。如果使用栈，c就会在栈底，反过来后就是最后一个。

## 时间复杂度 ##

O(V+E)

**接下来以有向图，邻接表存储为例**

## 图 ##

![20200831195550396.PNG][] 半欧拉图

## 代码 ##

/*
    Project: euler_graph
    Date:    2020/08/31
    Author:  Frank Yu
    */
    #include<string>
    #include<vector>
    #include<unordered_map>
    #include<iterator>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    //邻接表
    unordered_map<string, vector<string>> adj;
    void show_adj()
    {
    	cout << "邻接表:" << endl;
    	for (auto p:adj)
    	{
    		for (auto q:p.second)
    		{
    			cout << p.first << "->" << q<<endl;
    		}
    	}
    }
    //当做栈使用
    vector<string> stk;
    //深度遍历
    void dfs(const string& curr) {
    	//找到点 且还有相邻边
    	while (adj.count(curr) && adj[curr].size() > 0) {
    		string tmp = adj[curr].back();
    		adj[curr].pop_back();
    		dfs(move(tmp));
    	}
    	stk.emplace_back(curr);
    }
    //Hierholzer 算法，根据邻接表，返回欧拉环游/回路
    vector<string> Hierholzer(string start,unordered_map<string, vector<string>> adj)
    {
    		dfs(start);
    		reverse(stk.begin(), stk.end());
    		return stk;
    }
    //主函数
    int main()
    {
    	vector<string> a;
    	a.emplace_back("b");
    	a.emplace_back("c");
    	vector<string> b;
    	b.emplace_back("a");
    	vector<string> c;
    	c.emplace_back("b");
    	//插入点a(b) 及点a(b)的边 形成邻接表
    	adj.emplace(make_pair("a",a));
    	adj.emplace(make_pair("b", b));
    	adj.emplace(make_pair("c", c));
    	show_adj();
    	vector<string> e_tour = Hierholzer("a", adj);
    	cout << "欧拉迹/通路、欧拉环游/回路:" << endl;
    	for (string p:e_tour)
    	{
    		cout << p << " ";
    	}
    	cout << endl;
    	return 0;
    }

1. unordered\_map使用哈希表存储，不排序，速度快；

2.stack底层使用vectoe、deque、list，这里使用vector代替stack，效率更高；

3.使用move函数，效率高；

4.使用emplace\_back插入，而不是push\_back，效率更高。

## 截图 ##

![20200831195923506.PNG][] 结果

# Fleury算法 #

效率低，暂时先不实现了。

## 作用 ##

寻找半欧拉图、欧拉图的欧拉迹、欧拉环游/回路。

## 内容 ##

## 时间复杂度 ##

O(V+E)^2

## 图 ##

## 代码 ##

## 截图 ##

未完待续...

更多数据结构与算法实现：[数据结构（严蔚敏版）与算法的实现（含全部代码）][Link 1]

喜欢本文的请动动小手点个赞，收藏一下，有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。

[2020083118505778.PNG]: /images/20221123/dc952df8f3b844a8a1c31c2fd22ea3e9.png
[20200831195550396.PNG]: /images/20221123/a92cdaadf0ce458489f3332cb74e8369.png
[20200831195923506.PNG]: /images/20221123/65ccaa03474449e284fdd83f6e7572fd.png
[Link 1]: https://blog.csdn.net/lady_killer9/article/details/82695895