大佬教程收集整理的这篇文章主要介绍了图论——欧拉图原理及其应用，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
Part one . 欧拉图相关定义
注意：以上定义中的图均为连通图
Part two . 欧拉图性质
a.欧拉路径中有且仅有1个出度-入度==1和1个入读-出度==1的点，其余所有点都满足出度==入度 。欧拉路径的起点为出度-入读==1的点。
b.欧拉回路中所有点都满足出度-入读==1。欧拉回路的起点可以是任意点。
2. 无向图中
a.欧拉路径中有2个奇度数的点。它的起点为这两个奇度数中较小的一个点。
b.欧拉回路中所有点的都为偶度数点。它的起点为任意点。
Part three . 寻找欧拉路径/回路
例题1：欧拉路径模板题
思路：拿到题先不急于判定图的连通性，而是先统计个点的出入度情况。如此，我们不仅可以初步判断此图是否为半欧拉图（一般题目的默认欧拉图也包含半欧拉图），若不满足度数条件就说明不存在半欧拉图，而且还可以在满足度数条件的基础上确定一个起点。而后直接将起点带入图中dfs搜索，搜索的同时还需要统计所有走走过的边的条数，用以判断此图是否联通。若此图联通，则统计数一定和题目所给边数相等，因为孤立的点和边在搜索时一定不会被遍历到。还需要注意的一点是题目重要求的是字典序最小的答案，那么我们只需要按照所有点的出边的权值的字典序给所有出边排序就可以了。最后将存起来的答案倒序输出即可。
上代码
查看代码
#define CRT SECURE NO WARNINGS
#include<cstdio>
#include<cString>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<cmath>
using namespace std;
const int n = 1e5 + 10;
vector<int> edge[n];//邻接表存图，最好用邻接表或者链式前向星，邻接矩阵容易炸空间
stack<int>ans;
int in[n], out[n],n,m,f1=0,f2=0,sta=1,del[n];
//del用以在搜索时记住上一次以u为出发点走到了哪条边，这样就不需要给走过的边一一进行标记了，初始都为0代表
//out in 记录点的出入度
//sta 存储起点
//f1 f2分别统计出度-入度==1和入度-出度==1的点的个数
void dfs(int X)
{
for (int i =del[x]; i <edge[x].size(); i=del[x])
{
del[x] = i + 1;
dfs(edge[x][i]);
}
ans.push(X);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
edge[u].push_BACk(v);//读入边，因为边的权值为u，故不再重复存储权值
in[v]++;
out[u]++;//统计出入度
}
for (int i = 1; i <= n; i++)
{
if (in[i] - out[i] == 1)
f1++;
if (out[i] - in[i] == 1)
f2++, sta = i;
if (abs(in[i] - out[i]) > 1)//若存在出入度相差>2的情况，则一定不满足题意，直接返回
{
printf("No\n"); return 0;
}
}
if ((f1==1&&f2==1)||(f1==0&&f2==0))//若满足欧拉回路或欧拉路径的第一个条件则进行下一步搜索
{
for (int i = 1; i <= n; i++)//对出边进行排序
{
sort(edge[i].begin(), edge[i].end());
}
dfs(sta);
while(!ans.empty())//利用栈的后进先出性质完成答案的输出
{
printf("%d ",ans.top());
ans.pop();
}
puts("");
}
else//若不满足初步条件就直接跳出
printf("No\n");
return 0;
}
例题2：欧拉图简单应用
分析：其实和上面的模板题没有太大区别，做法思路相同，只是需要进行一些转换。题中要求将首尾字母相同的单词连接在一起，其实就是将首字母作为起点，尾字母作为终点，而单词本身则进行编号处理作为边的权值，这样就成功地将本题转化为一个寻找字典序最小的欧拉路径问题。虽然大体上看着和例 1 没啥区别，但是值得注意的是边的权值不再是起点，因此dfs函数中需要加一个参数来记录边的权值。另外，本题中dfs类似于一个必须确定当前走这一步可行，才会记录上一步路的摸索前进的过程。
上代码
#define CRT SECURE NO WARNINGS
#include<cstdio>
#include<cString>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<cmath>
using namespace std;
const int n = 1e3 + 10;
struct node
{
int v, num;
String s;
};
vector<node> maps[27];//用以存储图
vector<String>tmp;//存储所有字母以便后面进行排序，输出答案
int n, in[27], out[27], maxn = -1, minn = 28, sta, f1, f2, k, flag, vis[n], del[n];
//maxn用来记录点的最大值，minn用以记录点的最小值,del用来标记在上一次当前点u已经遍历到哪条出边了
//vis用来标记已经走过并压入栈中的边的编号，主要是用来弥补这个dfs的缺陷
stack<int>ans;//倒序记录答案边的编号
bool cmp(node x, node y)
{
return x.s < y.s;
}
void dfs(int x, int num)//x为本层搜索的起点，num为上一层搜索过的边
{
if (flag)
return;
if (k == n)
flag = 1;
for (int i = del[x]; i < maps[x].size(); i = del[x])
{
del[x] = i + 1;
k++;
dfs(maps[x][i].v, maps[x][i].num);
}
if (!vis[num])
ans.push(num), vis[num]++;
}
int main()
{
scanf("%d", &n);
String t = "zzzzzzzzzzzzzzzzzzzzz";
for (int i = 0; i < n; i++)
{
String s;
cin >> s;
if (s < t)
t = s;//确定字典序最小的字母
tmp.push_BACk(s);
int u = (s[0] - 'a') + 1;
int v = (s[s.size() - 1] - 'a') + 1;
in[v]++;//记录点的出度与入度
out[u]++;
maps[u].push_BACk({ v,i,tmp[i] });//读入边的信息
maxn = max(v, max(maxn, u));
minn = min(v, min(minn, u));
}
sta = t[0] - 'a' + 1;//初始化起点为字典序最小的单词的首字母对应的数字
for (int i = minn; i <= maxn; i++)//对图中所有点进行出入度判定
{
if (in[i] - out[i] == 1 && (in[i] || out[i]))
f1++;
if (out[i] - in[i] == 1 && (in[i] || out[i]))
f2++, sta = i;
}
if (!((f1 == f2 == 1) || (f1 == 0 && f2 == 0))) {//初步确定图中是否含欧拉路
printf("***\n");
return 0;
}
for (int i = minn; i <= maxn; i++)//题目中要求满足条件的字典序最小的答案，故对每个点的所有出边进行排序
{
sort(maps[i].begin(), maps[i].end(), cmp);
}
dfs(sta, maps[sta][0].num);
if (!flag)//未遍历所有边不满足条件，直接跳出
{
printf("***\n");
return 0;
}
int mark = 1;
while (!ans.empty())//倒序输出答案
{
if (mark)
cout << tmp[ans.top()], ans.pop(), mark = 0;
else
cout << "." << tmp[ans.top()], ans.pop();
}
return 0;
}以上内容纯属个人理解，如有错误，欢迎纠正。
时间：2022.3.8
以上是大佬教程为你收集整理的图论——欧拉图原理及其应用全部内容，希望文章能够帮你解决图论——欧拉图原理及其应用所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。