频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
欧拉路径和欧拉回路及其应用解析
2019-12-16 16:03:08           
收藏   我要投稿

欧拉路径:在一个图中,从i点出发,能将每个边遍历一次最终达到j点的一条路径

欧拉回路:i=j时的欧拉路径

无向图

欧拉回路:在无向图中,只要每个点的度数均为偶数,那么必定存在欧拉回路。因为每个点的度是偶数,意味着总有成对的入边和出边,则不会出现卡在一个节点的情况。
这里写图片描述

欧拉路径:有且仅有两个点的度数为奇数,那么存在从其中一个点到另一个点的欧拉路径。
这里写图片描述

有向图

欧拉回路:所有点的入度等于出度,就存在一条欧拉回路。类似于无向图,每个节点都有成对的入边和出边,那么必定存在欧拉回路

欧拉路径:至多一个点的出度 = 入度 + 1 (起点) , 之多一个点的 入度 = 出度 + 1 (终点) 。

至此判断一个图是否存在欧拉回路和欧拉路径已经可以完成。
接下来是知道存在的条件下找出路径。也就是常规的dfs把每条边走一遍。但是注意,第一个栈底的是无路可走的节点,我们在按照栈输出就行,也就是逆序输出,原因如下:

例如 1 - > 2 -> (3 -> 2 ) -> 1 这是个存在环的回路, 但是也满足欧拉路径的要求。
我们在dfs时可以看做每条边都有概率执行, 因此我们会得到这个dfs序: 1 -> 2 -> 1 (然后回溯返回到2) -> 3 - > 2。 顺序输出的话,把一些行不通的路径也输出了 。逆序输出则保证了栈底的必须是第一个无路可走的节点,也就是终点。

// 有可能两个点之间存在多条边,那么可以用vis[x][i] -- ,减一次走一次
void dfs(int x)
{
 for(int i=0; i v);//存储路径上的边
cnt++;
  }
 }

 ans.push(x);//存储路径上的点
}

应用:

1、Uva 10054 The Necklace
题意:给你n个珠子,一个珠子分为两半有两种颜色,用1到50来表示50种不同的颜色。把这些珠子串起来,两个紧挨着的珠子要满足一个条件就是接触的那部分颜色要相同

例如(1,2)(2,4),两个珠子的接触部分颜色相同都为2。当然,因为珠子最后是连成环的,第一个珠子和最后一个珠子也会接触,也要买满足这个条件

先输入T,有T组数据

输入n,有n个珠子

下面n行每行两个数字表示这个珠子的两个颜色,然后问你能不能连成一条链,能的话输出任意一种连接情况即可,不能的话输出失败.

思路:

给定的珠子上的两个颜色,看出无向图两个点连上一条边。题目转化成无向图的欧拉回路是否存在,存在即输出。

代码:
#include 
#include 

using namespace std;

vectorG[100];
int vis[100][100];
int d[100];
void dfs(int x)
{
 for(int i=0; i0)
  {
vis[x][v]--;
vis[v][x]--;
dfs(G[x][i]);
printf("%d %d\n",v,x);

  }
 }

}

int main()
{
 int n,m;
 scanf("%d%d",&n,&m);
 while(m--)
 {
  int a,b;
  cin>>a>>b;
  G[a].push_back(b);
  d[a]++;
  d[b]++;
  vis[a][b] ++;
  vis[b][a] ++;
 }
 for(int i=1; i<=n; i++)
  if(d[i]%2)
  {
puts("some beads may be lost\n");
return 0;
  }

 dfs(1);

 return 0;
}
点击复制链接 与好友分享!回本站首页
上一篇:Java数组中插入元素教程
下一篇:JDK动态代理和CGLIB代理解析
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 第一门户--致力于做实用的IT技术学习网站