通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。
1 定义
欧拉通路(Euler tour)——通过图中每条边一次且仅一次，并且过每一顶点的通路。
欧拉回路 (Eulercircuit)——通过图中每条边一次且仅一次，并且过每一顶点的回路。
2 无向图是否具有欧拉通路或回路的判定
G有欧拉通路的充分必要条件为：G 连通，G中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。
G有欧拉回路(G为欧拉图)：G连通，G中均为偶度顶点。
3 有向图是否具有欧拉通路或回路的判定
D有欧拉通路：D连通，除两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。
D有欧拉回路(D为欧拉图)：D连通，D中所有顶点的入度等于出度。
(注意：这里说有向图连通，说的是有向图是弱连通图。即把有向图中的边变成无向边，只要该图连通，那么原有向图即是弱连通图。实际中可用并查集判断是否弱连通)
注意下面打印节点的代码，其实打印欧拉路径的节点轨迹可以先打印每条欧拉路上的边，然后取每条边的头结点即可(最后一条边还需要取尾部结点)。
对于一般的单词首尾相连的问题，一般都是转化为有向图的欧拉通路问题(而不是无向图)，比如”给你多个单词,问你能不能将所有单词组成这样一个序列:序列的前一个单词的尾字母与后一个单词的头字母相同”，如果你把每个单词看出无向的边，那么最终求出的欧拉通路可能存在两个单词尾部和尾部相连的情况。
例题：
欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？
Input
Output
每个测试用例的输出占一行，若欧拉回路存在则输出1，否则输出0。
Sample Input
3 3 1 2 1 3 2 3 3 2 1 2 2 3 0
Sample Output
1 0
直接上模板
#include
#include
using namespace std; const int maxn=1005; int visit[maxn],d[maxn][maxn],degree[maxn]; int n,m; void dfs(int s) //判断图是否联通 { visit[s]=1; for(int i=1;i<=n;i++) { if(d[s][i]&&!visit[i]) dfs(i); } } int main() { ios::sync_with_stdio(false); while(cin>>n&&n) { memset(visit,0,sizeof(visit)); memset(d,0,sizeof(d)); memset(degree,0,sizeof(degree)); cin>>m; int a,b; for(int i=0;i
>a>>b; d[a][b]=d[b][a]=1; degree[a]++; degree[b]++; } dfs(1); bool flag=true; for(int i=1;i<=n;i++) { if(!visit[i]) flag=false; if(degree[i]%2!=0) flag=false; } if(flag) cout<<"1"<
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/224296.html原文链接：https://javaforall.net
