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
例题2:欧拉图简单应用
分析:其实和上面的模板题没有太大区别,做法思路相同,只是需要进行一些转换。题中要求将首尾字母相同的单词连接在一起,其实就是将首字母作为起点,尾字母作为终点,而单词本身则进行编号处理作为边的权值,这样就成功地将本题转化为一个寻找字典序最小的欧拉路径问题。虽然大体上看着和例 1 没啥区别,但是值得注意的是边的权值不再是起点,因此dfs函数中需要加一个参数来记录边的权值。另外,本题中dfs类似于一个必须确定当前走这一步可行,才会记录上一步路的摸索前进的过程。
上代码
查看代码
#define CRT SECURE NO WARNINGS
#include
#include
#include
#include
#include
#include
#include
以上内容纯属个人理解,如有错误,欢迎纠正。
时间:2022.3.8
名称栏目:图论——欧拉图原理及其应用
文章转载:
http://6mz.cn/article/dsogodo.html