IDEA激活码目录
概念
欧拉迹/通路（一笔画）
通过图中每条边且行遍所有顶点的迹（每条边恰一次的途径），称为欧拉迹（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，效率更高。
截图
Fleury算法
效率低，暂时先不实现了。
作用
寻找半欧拉图、欧拉图的欧拉迹、欧拉环游/回路。
内容
时间复杂度
O(V+E)^2
图
代码
截图
未完待续...
