欧拉路与欧拉回路
发布时间
阅读量：
阅读量
欧拉路与欧拉回路
-
简介
-
-
定理相关
-
- 定理内容
- 举个栗子
-
- 欧拉路
-
欧拉回路
- 简单证明
-
代码实现
-
- 深度优先搜索（dfs）
-
- 邻接矩阵
-
vector
-
链式前向星
-
-
后记
简介
- 简单说就是能从图的 某一点 不重复地 走过图的所有点（并非点不重复，是边不重复），其所经过的路径为欧拉路
- 欧拉回路是一种欧拉路，它是在欧拉路的基础上要求最后回到起始点（即1-10点，从点1开始，欧拉路要求不重复走完路径1-9，欧拉回路要求最后回到点1）
定理相关
定理内容
奇点 ： 点上连接路的个数为奇数个的点
- 存在欧拉路的图，奇点有且仅有两个
- 存在欧拉回路的图，一定无奇点
举个栗子
欧拉路
汉字 “中” “日”等等
欧拉回路
简单证明
从一个奇点出发，到另一奇点，期间经过的偶点，因为点上的路径有偶数条，可进也可出，必然能通过（不像奇点，只能走一次）
无奇点的图，点上路径均有偶数条，可进也可出
代码实现
大部分题只找到一条路即可，可选择深度优先搜索
深度优先搜索（dfs）
邻接矩阵
int mapp[n][n]; //点数
void dfs(int xx) {
printf("%d " ,xx);
for(int j=1;j<=n;++j) {
if(mapp[xx][j]) {
mapp[xx][j]=0;
// mapp[j][xx]=0; 无向图
dfs(j);
}
}
}
int main() {
scanf("%d %d",&n,&m); //点数 边数
for(int i=1;i<=m;++i) {
scanf("%d %d",&u,&v); //始点 终点
degree[u]++; //度
degree[v]++;
mapp[u][v]=1;
// mapp[v][u]=1; //无向图
}
for(int i=1;i<=n;++i) {
if(degree[i]&1) { //按位与 效果等同于degreee[i]%2==1
st=i;
// break; 若路径要求从小到大，需break
}
}
dfs(st);
}vector
struct edge{
int to;
int vis;
};
vector <edge> vec_edge[n]; //点数
void dfs(int xx) {
printf("%d ",xx);
for(int i=0;i<v[xx].size();++i) {
if(!v[xx][i].vis) {
v[xx][i].vis=1;
// v[i][xx].vis=1; 无向图
dfs(v[xx][i].to);
}
}
}
int main() {
scanf("%d %d",&n,&m); //点数 边数
for(int i=1;i<=m;++i) {
scanf("%d %d",&u,&v); //始点 终点
degree[u]++;
degree[v]++;
vec_edge[u].push_back(v);
// vec_edge[v].push_back(v);
}
for(int i=1;i<=n;++i) {
if(degree[i]&1) { //按位与 效果等同于degreee[i]%2==1
st=i;
// break; 若路径要求从小到大，需break
}
}
dfs(st);
}链式前向星
struct edge{
int to;
int vis;
}e;
void add_edge(int uu,int vv) {
tot++;
e[tot].next=head[uu];
e[tot].vis=0;
e[tot].to=vv;
}
int head[n];
void dfs(int xx) {
printf("%d ",xx);
for(int i=head[xx];i;i=e[i].next) {
if(e[i].vis) continue;
e[i].vis=1;
dfs(e[i].to);
}
}
int main() {
scanf("%d %d",&n,&m); //点数 边数
for(int i=1;i<=m;++i) {
scanf("%d %d",&u,&v); //始点 终点
degree[u]++;
degree[v]++;
add_edge(u,v);
// add_edge(v,u);
}
for(int i=1;i<=n;++i) {
if(degree[i]&1) { //按位与 效果等同于degreee[i]%2==1
st=i;
// break; 若路径要求从小到大，需break
}
}
dfs(st);
}后记
相关代码含义参见上一篇博客
图与存图
全部评论 (0)
还没有任何评论哟~