首页 > 代码库 > 欧拉回路与欧拉路 之 一笔画问题
欧拉回路与欧拉路 之 一笔画问题
一笔画问题
如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。
我们定义奇点是指跟这个点相连的边数目有奇数个的点。对于能够一笔画的图，我们有以下两个定理。
定理1：存在欧拉路的条件：图是连通的，有且只有2个奇点。
定理2：存在欧拉回路的条件：图是连通的，有0个奇点。
两个定理的正确性是显而易见的，既然每条边都要经过一次，那么对于欧拉路，除了起点和终点外，每个点如果进入了一次，显然一定要出去一次，显然是偶点。对于欧拉回路，每个点进入和出去次数一定都是相等的，显然没有奇点。
一笔画性质：
■⒈凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。
■⒉凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点为终点。
■⒊其他情况的图都不能一笔画出。(奇点数除以二便可算出此图需几笔画成。)
求欧拉路的算法很简单，使用深度优先遍历即可。
根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行DFS，时间复杂度为O(m+n)，m为边数，n是点数。
l样例输入:第一行n，m，有n个点，m条边，以下m行描述每条边连接的两点。
l 5 5
l 1 2
l 2 3
l 3 4
l 4 5
l 5 1
l样例输出:欧拉路或欧拉回路
l 1 5 4 3 2 1
欧拉路：
1 //欧拉路 2 3 #include<iostream> 4 #include<cstdio> 5 using namespace std; 6 int maps[1001][1001]; 7 int flag[1001]; 8 int tot,n,m; 9 int ans[1001],p=0;10 void dfs(int num){11 for(int i=1;i<=m;i++)12 if(maps[num][i]==1)13 {14 maps[num][i]=0;15 maps[i][num]=0;16 dfs(i);17 ans[++p]=i;18 }19 }20 int main()21 {22 int a,b,flag1=0,start=1;23 scanf("%d%d",&m,&n);24 for(int i=1;i<=n;i++)25 {26 scanf("%d%d",&a,&b);27 maps[a][b]=1;28 maps[b][a]=1;29 flag[a]++;30 flag[b]++;31 }32 for(int i=1;i<=n;i++)33 {34 if(flag[i]%2!=0)35 {36 if(flag1==0)37 start=i;38 flag1++;39 }40 if(flag1>2)41 {42 printf("Impossible");43 return 0;44 }45 }46 dfs(start);//必须从奇点开始搜 47 for(int i=1;i<=p;i++)48 printf("%d ",ans[i]);49 return 0; 50 }
欧拉回路：
似乎比欧拉路还水：从1开始搜的；
1 //欧拉回路 2 3 #include<iostream> 4 #include<cstdio> 5 using namespace std; 6 int maps[1001][1001]; 7 int flag[1001]; 8 int n,m; 9 int ans[1001],p=0;10 void dfs(int num){//搜哦搜 11 for(int i=1;i<=m;i++)12 if(maps[num][i]==1)13 {14 maps[num][i]=0;15 maps[i][num]=0;16 dfs(i);17 ans[++p]=i;18 }19 }20 int main()21 {22 int a,b,flag1=0;23 scanf("%d%d",&m,&n);24 for(int i=1;i<=n;i++)25 {26 scanf("%d%d",&a,&b);27 maps[a][b]=1;28 maps[b][a]=1;29 flag[a]++;30 flag[b]++;31 }32 for(int i=1;i<=n;i++)33 {34 if(flag[i]%2!=0)35 {36 printf("Impossible");37 return 0;38 }39 }40 dfs(1);//满足的话从哪个点搜都可以； 41 for(int i=1;i<=p;i++)42 printf("%d ",ans[i]);43 printf("%d ",1);44 return 0; 45 }
欧拉回路与欧拉路 之 一笔画问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。