图论——欧拉图原理及其应用

Part one . 欧拉图相关定义

创新互联建站专注为客户提供全方位的互联网综合服务，包含不限于做网站、成都网站制作、东明网络推广、小程序开发、东明网络营销、东明企业策划、东明品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；创新互联建站为所有大学生创业者提供东明建站搭建服务，24小时服务热线：13518219792，官方网址：www.cdcxhl.com

从某一特定起点出发不重复的遍历完所有边的路径叫做欧拉路径，具有欧拉路径的图叫做半欧拉图
从图中任意一点出发不重复地遍历完所有边并回到起点的回路叫做欧拉回路，具有欧拉回路的图即欧拉图

注意：以上定义中的图均为连通图

Part two . 欧拉图性质

有向图中

a.欧拉路径中有且仅有1个出度-入度==1和1个入读-出度==1的点，其余所有点都满足出度==入度。欧拉路径的起点为出度-入读==1的点。

b.欧拉回路中所有点都满足出度-入读==1。欧拉回路的起点可以是任意点。

2. 无向图中

a.欧拉路径中有2个奇度数的点。它的起点为这两个奇度数中较小的一个点。

b.欧拉回路中所有点的都为偶度数点。它的起点为任意点。

Part three . 寻找欧拉路径/回路

例题1：欧拉路径模板题

思路：拿到题先不急于判定图的连通性，而是先统计个点的出入度情况。如此，我们不仅可以初步判断此图是否为半欧拉图（一般题目的默认欧拉图也包含半欧拉图），若不满足度数条件就说明不存在半欧拉图，而且还可以在满足度数条件的基础上确定一个起点。而后直接将起点带入图中dfs搜索，搜索的同时还需要统计所有走走过的边的条数，用以判断此图是否联通。若此图联通，则统计数一定和题目所给边数相等，因为孤立的点和边在搜索时一定不会被遍历到。还需要注意的一点是题目重要求的是字典序最小的答案，那么我们只需要按照所有点的出边的权值的字典序给所有出边排序就可以了。最后将存起来的答案倒序输出即可。

上代码

查看代码

#define  CRT SECURE NO WARNINGS
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N = 1e5 + 10;
vector edge[N];//邻接表存图，最好用邻接表或者链式前向星，邻接矩阵容易炸空间
stackans;
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  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
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N = 1e3 + 10;
struct node
{
	int v, num;
	string s;
};
vector maps[27];//用以存储图
vectortmp;//存储所有字母以便后面进行排序，输出答案
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的缺陷
stackans;//倒序记录答案边的编号
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

当前名称：图论——欧拉图原理及其应用
文章URL：http://cdxtjz.cn/article/dsogodo.html

图论——欧拉图原理及其应用

其他资讯