欧拉回路算法

1 基本概念

1.1 欧拉路径和欧拉回路

欧拉路径:欧拉路是指从图中任意一个点开始到图中任意一个点结束的路径,并且图中每条边通过的且只通过一次
欧拉回路:欧拉回路是指起点和终点相同的欧拉路。
注意:如果欧拉回路,那么一定存在欧拉路径

注意: 是每条边被访问一次节点可能会被访问两次。

充分必要条件:
对于无向图,所有边都是连通的

(1)存在欧拉路径的充分必要条件:

  • 度数为奇数的点只能是0个或者2个

(2)存在欧拉回路的充分必要条件:

  • 度数为奇数的只能是0个

对于有向图,所有边都是连通的

(1)存在欧拉路径的充分必要条件:

  • 要么所有点的出度均等于入度。
  • 要么除了两个点之外,其余所有点的出度等于入度,剩余的两个点:一个满足出度比入度多1(起点),另一个满足入度比出度多1(终点)。

(2)存在欧拉回路的充分必要条件:

  • 所有点的出度均等于入度

2 欧拉路径判定算法

2.1 Fleury(弗罗莱) 算法

Fleury算法用来判断图是否是欧拉路径或欧拉回路的算法。
使用如下的欧拉图,了解Fleury算法的主要步骤。
在这里插入图片描述

  • 选节点1为起点,并将该起点加入路径中。Fleury算法选择存储欧拉路径。
    在这里插入图片描述
  • 从起点开始,一路DFS试着走出一条通路。方法是找与此节点相邻的节点。
    如果只有一个节点,则将这个点直接加入路径中。
    如果有多个相邻节点,则选择其中一条边,把相邻节点加入路径后,且删除这一条边。
    如果没有邻接节点,则从路径中弹出
    节点5和节点2都与1相邻,可以选择向5方向,也可以选择2方向。这里选择2方向,把节点2放入路径,然后置1-2这条边为删除状态。如此这般,一路经过3、4、5节点后回到1号节点。下图中标记为红色的边表示已经访问或被删除。
    在这里插入图片描述
  • 重新回到节点1,此时不再存在与节点1邻接的节点,从路径中弹也,依次可弹出5、4、3。直到碰到2号节点。
    在这里插入图片描述
  • 因为存在与2号节点邻接的节点,再次以2号节点为始点,使用DFS开路。一路上遇到6、7,且再次回到2号节点。
    在这里插入图片描述
  • 2号节点不存在与之邻接的节点,出栈。同理,7、6依次出栈。
    在这里插入图片描述
    小结:
    当有与当前节点邻接的节点时,一路DFS,直到没有邻接的尽头。些时,一轮DFS算法结束,从路径中依次弹出没有邻接节点的节点,直到遇到还有邻接节点的节点,新一轮的DFS重新开始。直到所有节点邻接的边全部访问完毕。
    编码实现:
#include <iostream>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <stack>
#define INF 100000
using namespace std;
int graph[100][100];
int n,m;
stack<int> sta;
void read() {
	for(int i = 0; i < m; i++) {
		int f,t;
		cin >> f >> t;
		graph[f][t] = 1;
		graph[t][f] = 1;
	}
}
void dfs(int u) {
	sta.push(u);
	for(int i = 1; i <= n; i++) {
		if(graph[i][u] > 0) {
			//标记为删除
			graph[u][i] = 0;
			graph[i][u] = 0;
			dfs(i);
			//仅朝一条边方向 DFS,方便形成回路 
			break;
		}
	}
}
void fleury(int x) {
	int  isEdge;
	sta.push(x);
	while(!sta.empty()) {
		isEdge = 0;
		int t = sta.top();
		sta.pop();
		//检查是否有边
		for(int i = 1; i <= n; i++) {
			if(graph[t][i] > 0) {
				isEdge = 1;
				break;
			}
		}
		if(isEdge == 0) {
			//没有邻接边,输出
			cout << t << " ";
		} else {
			//有邻接边,一路DFS狂奔
			dfs(t);
		}
	}
}
int main() {
	cin >> n >> m;
	memset(graph,0,sizeof(graph));
	read();
	int num = 0;
	int start = 1;
	for(int i = 1; i <= n; i++) {
		int deg = 0;
		for(int j = 1; j <= n; j++)
			deg += graph[i][j];
		if(deg % 2 == 1) {
			//奇节点的数量
			start = i;
			num++;
		}
	}
	if(num == 0 || num == 2)
		fleury(start);
	else
		cout << "不存在欧拉路径" << endl;
	return 0;
}
//测试用例
7 8
1 2
1 5
2 3
2 6
2 7    
3 4
4 5
6 7    

测试结果
在这里插入图片描述

from typing import List
from collections import defaultdict


class Solution:
    def __init__(self):
        self.G = defaultdict(list)
        self.degree = defaultdict(int)
        self.res = []
        
    def dfs(self, start):
        for j in self.G[start]:
            if j in self.G[start]:
                self.G[start].remove(j)
                self.G[j].remove(start)
                self.dfs(j)
        self.res.append(start)


    def fleury(self, connects) -> List:
        for con in connects:
            self.G[con[0]].append(con[1])
            self.degree[con[0]] += 1
            self.G[con[1]].append(con[0])
            self.degree[con[1]] += 1
        start = connects[0][0]
        cnt = 0
        for k,v in self.degree.items():
            if v %2 != 0:
                cnt += 1
                start = k
        if cnt == 0 or cnt == 2:
            self.dfs(start)
        else:
            print("不存在欧拉路径")
            return []
        return self.res
        

if __name__ == "__main__":
    so = Solution()
    connects = [[1,2], [2,3], [3,4],[4,5],[5, 1],[2,6],[6,7],[7,2]]
    res = so.fleury(connects)
    print(res)
        

2.2 Hierholzer 算法

也称逐步插入回路法。由数学家卡尔·希尔霍尔策给出,基于贪心思想。Hierholzer 的基本思路。先找到一个子回路,以此子回路为基础,逐步将其它回路以插入的方式合并到该子回路中,最终形成完整的欧拉回路。继续使用上图做演示。

  • 寻找子回路:如下从节点1开始,沿着边遍历图,一边遍历一边删除经过的边。如果遇到一个所有边都被删除的节点,那么该节点必然是 1(回到初始点)。将该回路上的节点和边添加到结果序列中。这个过程和Fleury算法没有太多区别。
    在这里插入图片描述

  • 回溯时检查刚添加到结果序列中的节点,看是否还有与节点相连且未遍历的边。可发现节点 2 有未遍历的边,则从 2 出发开始遍历,找到一个包含2 的新回路,将结果序列中的一个 2 用这个新回路替换,此时结果序列仍然是一个回路。这是和Fleury算法最大区别。
    在这里插入图片描述

  • 重复直到所有边都被遍历。

编码实现:

#include<iostream>
#include<string.h>
#include<vector>

const int maxn = 10005;
const int maxm = 1000005;//edge
using namespace std;
int n,m;
struct Edge {
	int to, nxt;
	bool vis=0;
};
Edge edge[maxm];
//如果没有以 i 为起点的有向边则 head[i] 的值为 0
int head[maxm];
//边的个数
int cnt;
//存储找到的回路
vector<Edge> ans;
//起始点
int sn;

void init() {
	for(int i=1; i<=n; i++) {
		head[i]=0;
		cnt=0;
	}
}

/*
*添加边
*/
void addEdge(int from, int to) {
	edge[cnt].to = to;
	edge[cnt].nxt = head[from];
	head[from] = cnt++;
}
void read() {
	int f,t;
	for(int i=1; i<=m; i++) {
		cin>>f>>t;
		addEdge(f,t);
		addEdge(t,f);
	}
}
void hierholzer(int sn) {
	for (int i = head[sn]; i != 0; i = edge[i].nxt) {
		// 遍历过
		if (edge[i].vis) continue;
		// 删除
		edge[i].vis = edge[i ^ 1].vis = true;
		// 继续
		hierholzer(edge[i].to);
		// 回溯时加入结果序列后,循环会继续查找是否有邻接边
		ans.push_back(edge[i]);
        
	}
}
void show() {
	for(int i=0; i<ans.size(); i++) {
		cout<<ans[i].to<<"\t";
	}
	cout<<sn<<"\t";
}

int main() {
	cin>>n>>m;
	sn=1;
	init();
	read();
	hierholzer(sn);
	show();
	return 0;
}

测试结果:
在这里插入图片描述

3. 总结

Hierholzer和Fleury算法的基本思路差不多,在DFS时找环。Fleury使用分段策略,找到一条环后,以环中某一个还存在邻接边的节点重新开始使用DFS找环,直到找到所有环。Hierholzer算法很有技巧性,在回溯时检查节点是否还有邻接边,有则重新DFS直到完毕。

参考资料:
https://blog.csdn.net/y6123236/article/details/135020029
https://blog.csdn.net/binggui2/article/details/108540016

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/543718.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

策略模式【行为模式C++】

1.概述 策略模式是一种行为设计模式&#xff0c; 它能让你定义一系列算法&#xff0c; 并将每种算法分别放入独立的类中&#xff0c; 以使算法的对象能够相互替换。 策略模式通常应用于需要多种算法进行操作的场景&#xff0c;如排序、搜索、数据压缩等。在这些情况下&#x…

【C++]C/C++的内存管理

这篇博客将会带着大家解决以下几个问题 1. C/C内存分布 2. C语言中动态内存管理方式 3. C中动态内存管理 4. operator new与operator delete函数 5. new和delete的实现原理 6. 定位new表达式(placement-new) 1. C/C内存分布 我们先来看下面的一段代码和相关问题 int global…

Unity 通过权重做随机

我们可以通过Random.Range方法结合权重来实现随机选择。具体步骤如下&#xff1a; 首先&#xff0c;创建一个数组&#xff0c;其中包含你要选择的项目&#xff0c;并为每个项目分配一个权重值。 计算所有权重值的总和。 使用Random.Range生成一个介于0和总权重之间的随机数。…

Hadoop+Spark大数据技术(微课版)曾国荪、曹洁版思维导图第四次作业 (第4章 HBase分布式DB)

1.简述Hbase的特点及与传统关系数据库的区别 HBase与传统关系数据库的区别 &#xff08;1&#xff09;数据类型 关系数据库具有丰富的数据类型&#xff0c;如字符串型、数值型、日期型、二进制型等。HBase只有字符串数据类型&#xff0c;数据的实际类型都是交由用户自己编写程序…

Google Imagen 2对比OpenAI的Dall-E 3 - 同一提示,不同结果

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

python怎么输出小数

先将整型转换成float型&#xff0c;再进行计算&#xff0c;结果就有小数了。 >>> a 10 >>> b 4 >>> c a/b >>> a,b,c (10, 4, 2) >>> a float(a) >>> d a/b >>> a,b,d (10.0, 4, 2.5) >>> 注意&…

1036: 寻找整数序列的主元素

解法&#xff1a; #include<iostream> #include<vector> #include<algorithm> using namespace std; int main() {int n;cin >> n;vector<int> arr(n);vector<int> tong(1000);for (auto& x : arr) {cin >> x;tong[x];}int pma…

如何在Windows安装LocalSend并结合内网穿透实现公网跨平台远程文件互传

文章目录 1. 在Windows上安装LocalSend2. 安装Cpolar内网穿透3. 公网访问LocalSend4. 固定LocalSend公网地址 本篇文章介绍在Windows中部署开源免费文件传输工具——LocalSend&#xff0c;并且结合cpolar内网穿透实现公网远程下载传输文件。 localsend是一款基于局域网的文件传…

宜搭无权查询该应用信息,唯一排查码:21081d4e17130865292352743e9ed8

这种问题可能是关联表单出现了问题&#xff0c;当前应用中没有这个表单 所以就出现了应用无权访问的问题

备战蓝桥杯(日益更新)(刷题)

备战蓝桥杯&#xff08;日益更新&#xff09;&#xff08;刷题&#xff09; 文章目录 备战蓝桥杯&#xff08;日益更新&#xff09;&#xff08;刷题&#xff09;前言&#xff1a;一、二分&#xff1a;1. acwing503 借教室&#xff1a;&#xff08;二分 差分&#xff09;2. ac…

荔枝派LicheePi 4A RISCV板子支持的好玩的AI模型

荔枝派LicheePi 4A 是基于 Lichee Module 4A 核心板的 高性能 RISC-V Linux 开发板&#xff0c;以 TH1520 为主控核心&#xff08;4xC9101.85G&#xff0c; RV64GCV&#xff0c;4TOPSint8 NPU&#xff0c; 50GFLOP GPU&#xff09;&#xff0c;板载最大 16GB 64bit LPDDR4X&…

JavaScript(七)-高级技巧篇

文章目录 深浅拷贝浅拷贝深拷贝 异常处理thorw抛异常try/catch捕获异常debugger 处理thisthis指向改变this 性能优化防抖lodash实现防抖手写防抖函数 节流 - throttle 深浅拷贝 浅拷贝 深拷贝 深拷贝有三种方式 通过递归实现深拷贝 一定先写数组再写对象 lodash/cloneDeep …

PostgreSQL入门到实战-第二十八弹

PostgreSQL入门到实战 PostgreSQL中数据分组操作(三)官网地址PostgreSQL概述PostgreSQL中GROUPING SETS命令理论PostgreSQL中GROUPING SETS命令实战更新计划 PostgreSQL中数据分组操作(三) 使用PostgreSQL grouping sets子句在查询中生成多个分组集。 官网地址 声明: 由于操…

[尚硅谷flink] 检查点笔记

在Flink中&#xff0c;有一套完整的容错机制来保证故障后的恢复&#xff0c;其中最重要的就是检查点。 文章目录 11.1 检查点11.1.1 检查点的保存1&#xff09;周期性的触发保存2&#xff09;保存的时间点3&#xff09;保存的具体流程 11.1.2 从检查点恢复状态11.1.3 检查点算法…

linux 内存寻址

&#xff08;持续更新&#xff09; 相关概念 查看的书籍为 深入linux内核 内存地址 当使用80x86&#xff08;32位&#xff09;微处理器时&#xff0c;一般分为三种不同的地址&#xff1a; 逻辑地址 包含在机器语言指令中用来指定一个操作数或一条指令的地址。每一个逻辑地址…

【服务器配置】Portainer环境配置

Portainer环境配置 概述 Portainer 是一种用于管理 Docker 和 Kubernetes 容器的开源工具。通过其用户友好的 Web 界面&#xff0c;用户可以轻松管理容器、镜像、网络和卷等资源 拉去最新的Portainer docker pull portainer/portainer 安装和启动 docker run -d --restarta…

WindowsServer 2022 AD域控-006-安装副域控

试验拓扑图&#xff1a; 一、测试单域控故障&#xff0c;用户无法修改密码&#xff1b; 域控断网&#xff0c;Win10测试; 二、WindowsServer2022 DC02加入域控&#xff1b; 加入成功 此时域控上只有DC02这台服务器&#xff0c;但DC02并不是域控&#xff1b; 三、WindowsS…

『VUE』17. Dom与模板引用(详细图文注释)

目录 回顾之前的操作ref 属性借助dom使用原生js总结 欢迎关注 『VUE』 专栏&#xff0c;持续更新中 欢迎关注 『VUE』 专栏&#xff0c;持续更新中 回顾之前的操作 之前的这些操作都是我们使用vue为我们渲染的对象,再来操作dom 内容改变{{ 模板语法 }}属性改变 v-bind:添加事…

Java 中文官方教程 2022 版(二十九)

原文&#xff1a;docs.oracle.com/javase/tutorial/reallybigindex.html BCP 47 扩展 原文&#xff1a;docs.oracle.com/javase/tutorial/i18n/locale/extensions.html Java SE 7 版本符合 IETF BCP 47 标准&#xff0c;支持向Locale添加扩展。任何单个字符都可以用于表示扩展&…

2. Spring的创建和Bean的存取

经过前面的学习我们已经大体明白了 IOC 思想以及它的实现方式 DI &#xff0c;本节要讲的是如何Spring框架实现实现DI。 本节目标&#xff1a; Spring(Core) 项目创建将对象存储到 Spring 中将对象(bean)从 Spring 中取出 1. 创建 Spring 项目 与开篇演示的 Spring Boot 项目不…