有向图与无向图:欧拉路径&欧拉回路(一笔画)
2022/4/20 23:19:24
本文主要是介绍有向图与无向图:欧拉路径&欧拉回路(一笔画),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
咕了好久的图论的一小小小部分。
1、定义
欧拉路径 :不重复经过图上每一条边的路径
欧拉回路 : 起止点相同的欧拉路径
2、判定
$\bullet$ 有向图:
$\bullet$ 欧拉路径 :图中有且仅有 $1$ 个点出度比入度多 $1$ ,为起点;图中有且仅有 $1$ 个点入度比出度多 $1$ ,为终点;其余节点 入度 $=$ 出度。
$\bullet$ 欧拉回路 :图中所有点 入度 $=$ 出度,起止点为任意点。
$\bullet$ 有向图:
$\bullet$ 欧拉路径 :图中仅有 $2$ 个点度数为奇数,其余点度数为偶数,这两个奇数点可以任意选为起点终点。
$\bullet$ 欧拉回路 :所有点度数都是偶数,起止点任意。
其实这些概念还是很好理解的,有进就有出,否则肯定有走不通的,回路就是起止点连在一起了。
3、寻找
假设我们已经选好起点,那么一次对图的 dfs 即可求出,我们只需要用栈记录即可。
注意!如果题中要求按字典序,那最好是用 vector 或者邻接矩阵。
附上例题:传送门~。
哦对了,无向图的最好是只用邻接矩阵,不然删边很麻烦的!!
例题代码,算是有向图欧拉路径的板子,一个通了别的也通了。
#include<cstdio> #include<queue> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<cctype> #include<vector> #include<string> #include<climits> #include<stack> using namespace std; template <typename T> inline void read(T &x){ x=0;char ch=getchar();bool f=0; while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();} while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); if(f)x=-x; } template <typename T,typename ...Args> inline void read(T &tmp,Args &...tmps){read(tmp);read(tmps...);} const int N = 1e6 + 5; int in[N],out[N],n,m,now[N]; vector<int>g[N]; stack<int>s; int flag = 1,cnt[2],st = 1; inline void dfs(int u){ for(int i=now[u];i<g[u].size();i=now[u]){ now[u] = i + 1;//避免重复走 dfs(g[u][i]); } s.push(u);//记录,也可以手写栈更快 } signed main(){ read(n,m); for(int i=1;i<=m;++i){ int u,v; read(u,v); g[u].push_back(v); in[v]++; out[u]++; //统计结点入度出度,如果是无向图统一一个数组记录度 } for(int i=1;i<=n;++i)sort(g[i].begin(),g[i].end());//题里要字典序,忽略啦~ for(int i=1;i<=n;++i){ if(in[i] != out[i])flag = 0; if(out[i] == in[i] + 1)cnt[1]++,st = i; if(in[i] == out[i] + 1)cnt[0]++; } if((!flag) && !(cnt[0] == cnt[1] && cnt[0] == 1))return printf("No"),0;//既没有回路也没有路径 dfs(st); while(!s.empty())printf("%d ",s.top()),s.pop();//输出 }
这篇关于有向图与无向图:欧拉路径&欧拉回路(一笔画)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?