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

目录概念欧拉迹/通路（一笔画）半欧拉图环游欧拉环游/回路欧拉图欧拉定理推论Hierholzer 算法作用内容时间复杂度图代码截图Fleury算法作用内容时间复杂度图代码截图概念欧拉迹/通路（一笔画）通过图中每条边且行遍所有顶点的迹（每条边恰一次的途径），称为欧拉迹（Euler trail）。半欧拉图具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图，有且仅有两个度数为奇数的结点。环游图的环游(t

lady_killer9

12093人浏览 · 2020-08-31 20:08:24

lady_killer9 · 2020-08-31 20:08:24 发布

概念

欧拉迹/通路（一笔画）

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

半欧拉图

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

环游

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

欧拉环游/回路

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

欧拉图

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

欧拉定理

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

推论

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

Hierholzer 算法

作用

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

内容

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

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

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

a加入队列。

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

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

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

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

时间复杂度

O(V+E)

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

图

邻接表
a->b->c
b->a
c->b

代码

/*
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，效率更高。