admin 管理员组

文章数量: 888526

欧拉道路 和 欧拉回路

经典的七桥问题：是否存在一条路线，可以不重复的走遍7座桥。

转化为图就是，是否存在一条路线，可以不重复地走遍所有边。

所以在欧拉道路中，“进”和“出”是相对应的——除了起点和终点外，每个点的人度和出度相等。就是说除了起点和终点，其它点的度数应是偶数。

所以存在欧拉道路的充分条件是：

无向图：

一：要连通。

二：如果存在两个奇度点，则为起点和终点，此为欧拉道路。不存在，则起点是任意的，此为欧拉回路。

有向图：

一：连通。

二：最多只有两个点的人度不等于出度，而且必须是一个点的出度比人度大1（起点），另一个点的人度比出度大1（终点），此为欧拉道路。

        每个点的人度等于出度，此为欧拉回路。

判断连通性：BFS ， DFS ，并查集。

然后，无向图判断是否存在奇度点。有向图判断是否存在人度大于出度和出度大于人度的点。


void euler(int u)
{for(int v = 0; v < n; v ++){if(g[u][v] && !vis[u][v]){printf("%d %d",u , v);vis[u][v] = vis[v][u];//有向图只有一条边。euler(v);}}
}

UVa

10054 - The Necklace


.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=995


代码如下：

#include <cstdio>
#include <cstring>
#include <stack>
#define Max 60
using namespace std;
int map[Max][Max];
int in[Max];
//struct E{ int u, v; } tmp;
int n ;
void euler( int u )
{for ( int v = 1; v < n; ++v ) if ( map[u][v] ){map[u][v]--; map[v][u] = map[u][v];printf("%d %d\n", u, v);euler( v );}
}
int main()
{int T,a,b;scanf("%d",&T);for(int cas=1;cas<=T;cas++){scanf("%d",&n);memset(map,0,sizeof(map));memset(in,0,sizeof(in));for(int i=0;i<n;i++){scanf("%d%d",&a,&b);++in[a];++in[b];++map[a][b];map[b][a]=map[a][b];}bool ok=true;for(int i=0;i<=50;i++){if(in[i]%2)//项链要求是欧拉回路，不能是欧拉道路。ok=false;}printf("Case #%d\n",cas);if(!ok)printf("some beads may be lost\n");else{euler(a);}printf("\n");}return 0;
}


本文标签： 欧拉道路 和 欧拉回路

版权声明：本文标题：欧拉道路 和 欧拉回路 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1686635357h20002.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。