欧拉回路

难...

详细描述一下算法。回答你的问题时，只答程序有关的，算法是你的，需要你提供

　　若图G中存在这样一条路径，使得它恰通过G中每条边一次，则称该路径为欧拉路径。若该路径是一个圈，则称为欧拉回路。 　　具有欧拉回路的图称为欧拉图。具有欧拉路径但不具有欧拉回路的图称为半欧拉图。 　　无向图存在欧拉回路的充要条件： 　　一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。 　　有向图存在欧拉回路的充要条件： 　　一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。

以下判断基于此图的基图连通。无向图存在欧拉回路的充要条件一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。有向图存在欧拉回路的充要条件一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。混合图存在欧拉回路条件要判断一个混合图G（V,E）（既有有向边又有无向边）是欧拉图，方法如下：假设有一张图有向图G"，在不论方向的情况下它与G同构。并且G"包含了G的所有有向边。那么如果存在一个图G"使得G"存在欧拉回路，那么G就存在欧拉回路。其思路就将混合图转换成有向图判断。实现的时候，我们使用网络流的模型。现任意构造一个G"。用Ii表示第i个点的入度，Oi表示第i个点的出度。如果存在一个点k，|Ok-Ik|mod 2=1，那么G不存在欧拉回路。接下来则对于所有Ii>Oi的点从源点连到i一条容量为(Ii-Oi)/2的边，对于所有Ii<Oi的点从i连到汇点一条容量为(Oi-Ii)/2的边。如果对于节点U和V，无向边（U，V）∈E，那么U和V之间互相建立容量为无限大的边。如果此网络的最大流等于∑|Ii-Oi|/2，那么就存在欧拉回路。

欧拉回路不一定是初级回路，需要判定。1、无向图存在欧拉回路的充要条件一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。2、有向图存在欧拉回路的充要条件一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。3、混合图存在欧拉回路条件要判断一个混合图G（V,E）（既有有向边又有无向边）是欧拉图，方法如下：假设有一张图有向图G"，在不论方向的情况下它与G同构。并且G"包含了G的所有有向边。那么如果存在一个图G"使得G"存在欧拉回路，那么G就存在欧拉回路。扩展资料注意record中的点的排列是输出的倒序，因此，如果要输出欧拉路径，需要将record倒过来输出。求欧拉回路的思路：循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法不保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。

图G的一个回路，若它恰通过G中每条边一次,则称该回路为欧拉(Euler)回路。具有欧拉回路的图称为欧拉图（简称E图）。无向图存在欧拉回路的充要条件一个无向图存在欧拉回路，当且仅当该图所有顶点度数都是偶数且该图是连通图。有向图存在欧拉回路的充要条件一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图，或者 一个顶点的度数为1，另一个度数为-1，其他顶点的度数为0。混合图存在欧拉回路条件要判断一个混合图G（V,E）（既有有向边又有无向边）是欧拉图，方法如下：假设有一张图有向图G"，在不论方向的情况下它与G同构。并且G"包含了G的所有有向边。那么如果存在一个图G"使得G"存在欧拉回路，那么G就存在欧拉回路。其思路就将混合图转换成有向图判断。实现的时候，我们使用网络流的模型。现任意构造一个G"。用Ii表示第i个点的入度，Oi表示第i个点的出度。如果存在一个点k，|Ok-Ik|mod 2=1，那么G不存在欧拉回路。接下来则对于所有Ii>Oi的点从源点连到i一条容量为(Ii-Oi)/2的边，对于所有Ii<Oi的点从i连到汇点一条容量为(Oi-Ii)/2的边。如果对于节点U和V，无向边（U，V）∈E，那么U和V之间互相建立容量为无限大的边。如果此网络的最大流等于∑|Ii-Oi|/2，那么就存在欧拉回路。编辑本段解法无向图欧拉回路解法求欧拉回路的一种解法下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路。C语言代码，不全，请不要直接粘贴。int num = 0;//标记输出队列int match[MAX];//标志节点的度，无向图，不区分入度和出度void solve(int x){if(match[x] == 0)Record[num++] = x;else{for(int k =0;k<=500;k++){if(Array[x][k] !=0 ){Array[x][k]--;Array[k][x]--;match[x]--;match[k]--;solve(k);}}Record[num++] = x;}}pascal代码:求无向图的欧拉回路（递归实现）program euler;const maxn=10000;{顶点数上限}maxm=100000;{边数上限}type tnode=^tr;tr=recordf,t:longint;{边的起始点和终止点}al:boolean;{访问标记}rev,next:tnode;{反向边和邻接表中的下一条边}end;var n,m,bl:longint;{顶点数，边数，基图的极大连通子图个数}tot:longint;g:array[1..maxn] of tnode;d:array[1..maxn] of longint;{顶点的度}fa,rank:array[1..maxn] of longint;{并查集中元素父结点和启发函数值}list:array[1..maxm] of tnode;{最终找到的欧拉回路}o:boolean;{原图中是否存在欧拉回路}procedure build(ta,tb:longint);{在邻接表中建立边(ta, tb)}var t1,t2:tnode;begint1:=new(tnode);t2:=new(tnode);t1^.f:=ta;t1^.t:=tb;t1^.al:=false;t1^.rev:=t2;t1^.next:=g[ta];g[ta]:=t1;t2^.f:=tb;t2^.t:=ta;t2^.al:=false;t2^.rev:=t1;t2^.next:=g[tb];g[tb]:=t2;end;procedure merge(a,b:longint);{在并查集中将a, b两元素合并}var oa,ob:longint;beginoa:=a;while fa[a]<>a do a:=fa[a];fa[oa]:=a;ob:=b;while fa[b]<>b do b:=fa[b];fa[ob]:=b;if a<>b then begindec(bl);{合并后，基图的极大连通子图个数减少1}if rank[a]=rank[b] then inc(rank[a]);if rank[a]>rank[b] then fa[b]:=a else fa[a]:=b;end;end;procedure init;{初始化}var i,ta,tb:longint;beginfillchar(fa,sizeof(fa),0);fillchar(rank,sizeof(rank),0);fillchar(d,sizeof(d),0);readln(n,m);for i:=1 to n do fa[i]:=i;bl:=n;for i:=1 to m do beginreadln(ta,tb);build(ta,tb);inc(d[tb]);inc(d[ta]);merge(ta,tb);end;end;procedure search(i:longint);{以i为出发点寻找欧拉回路}var te:tnode;beginte:=g[i];while te<>nil do beginif not te^.al then beginte^.al:=true;te^.rev^.al:=true;search(te^.t);list[tot]:=te;dec(tot);end;te:=te^.next;end;end;procedure main;{主过程}var i:longint;begino:=false;for i:=1 to n doif d[i]=0 then dec(bl);{排除孤立点的影响}if bl<>1 then exit;{原图不连通，无解}for i:=1 to n doif odd(d[i]) then exit;{存在奇点，无解}o:=true;for i:=1 to n doif d[i]<>0 then break;tot:=m;search(i);{从一个非孤立点开始寻找欧拉回路}end;procedure print;{输出结果}var i:longint;beginif not o then writeln("No solution.") else beginwriteln(list[1]^.f);for i:=1 to m do writeln(list[i]^.t);end;end;begininit;main;print;end.注意record中的点的排列是输出的倒序，因此，如果要输出欧拉路径，需要将record倒过来输出。求欧拉回路的思路：循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法不保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。具体步骤：1。如果此时与该点无相连的点，那么就加入路径中2。如果该点有相连的点，那么就加入队列之中，遍历这些点，直到没有相连的点。3。处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。4。这个其实是个递归过程。

欧拉路径包括欧拉路（不形成回路）和欧拉回路两种情况。 连通无向图，当有零个奇数度节点，即没有奇数度节点，此时所有节点度数都是偶数，一定有欧拉回路。具有欧拉回路的图称为欧拉图。 连通无向图，当只有两个奇数度节点，其他节点度数都为偶数时，一定有欧拉路。

图G的一个回路，若它恰通过G中每条边一次,则称该回路为欧拉(Euler)回路。具有欧拉回路的图称为欧拉图（简称E图）。无向图存在欧拉回路的充要条件一个无向图存在欧拉回路，当且仅当该图所有顶点度数都是偶数且该图是连通图。有向图存在欧拉回路的充要条件一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图，或者 一个顶点的度数为1，另一个度数为-1，其他顶点的度数为0。混合图存在欧拉回路条件要判断一个混合图G（V,E）（既有有向边又有无向边）是欧拉图，方法如下：假设有一张图有向图G"，在不论方向的情况下它与G同构。并且G"包含了G的所有有向边。那么如果存在一个图G"使得G"存在欧拉回路，那么G就存在欧拉回路。其思路就将混合图转换成有向图判断。实现的时候，我们使用网络流的模型。现任意构造一个G"。用Ii表示第i个点的入度，Oi表示第i个点的出度。如果存在一个点k，|Ok-Ik|mod 2=1，那么G不存在欧拉回路。接下来则对于所有Ii>Oi的点从源点连到i一条容量为(Ii-Oi)/2的边，对于所有Ii<Oi的点从i连到汇点一条容量为(Oi-Ii)/2的边。如果对于节点U和V，无向边（U，V）∈E，那么U和V之间互相建立容量为无限大的边。如果此网络的最大流等于∑|Ii-Oi|/2，那么就存在欧拉回路。编辑本段解法无向图欧拉回路解法求欧拉回路的一种解法下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路。C语言代码，不全，请不要直接粘贴。int num = 0;//标记输出队列int match[MAX];//标志节点的度，无向图，不区分入度和出度void solve(int x){if(match[x] == 0)Record[num++] = x;else{for(int k =0;k<=500;k++){if(Array[x][k] !=0 ){Array[x][k]--;Array[k][x]--;match[x]--;match[k]--;solve(k);}}Record[num++] = x;}}pascal代码:求无向图的欧拉回路（递归实现）program euler;const maxn=10000;{顶点数上限}maxm=100000;{边数上限}type tnode=^tr;tr=recordf,t:longint;{边的起始点和终止点}al:boolean;{访问标记}rev,next:tnode;{反向边和邻接表中的下一条边}end;var n,m,bl:longint;{顶点数，边数，基图的极大连通子图个数}tot:longint;g:array[1..maxn] of tnode;d:array[1..maxn] of longint;{顶点的度}fa,rank:array[1..maxn] of longint;{并查集中元素父结点和启发函数值}list:array[1..maxm] of tnode;{最终找到的欧拉回路}o:boolean;{原图中是否存在欧拉回路}procedure build(ta,tb:longint);{在邻接表中建立边(ta, tb)}var t1,t2:tnode;begint1:=new(tnode);t2:=new(tnode);t1^.f:=ta;t1^.t:=tb;t1^.al:=false;t1^.rev:=t2;t1^.next:=g[ta];g[ta]:=t1;t2^.f:=tb;t2^.t:=ta;t2^.al:=false;t2^.rev:=t1;t2^.next:=g[tb];g[tb]:=t2;end;procedure merge(a,b:longint);{在并查集中将a, b两元素合并}var oa,ob:longint;beginoa:=a;while fa[a]<>a do a:=fa[a];fa[oa]:=a;ob:=b;while fa[b]<>b do b:=fa[b];fa[ob]:=b;if a<>b then begindec(bl);{合并后，基图的极大连通子图个数减少1}if rank[a]=rank[b] then inc(rank[a]);if rank[a]>rank[b] then fa[b]:=a else fa[a]:=b;end;end;procedure init;{初始化}var i,ta,tb:longint;beginfillchar(fa,sizeof(fa),0);fillchar(rank,sizeof(rank),0);fillchar(d,sizeof(d),0);readln(n,m);for i:=1 to n do fa[i]:=i;bl:=n;for i:=1 to m do beginreadln(ta,tb);build(ta,tb);inc(d[tb]);inc(d[ta]);merge(ta,tb);end;end;procedure search(i:longint);{以i为出发点寻找欧拉回路}var te:tnode;beginte:=g[i];while te<>nil do beginif not te^.al then beginte^.al:=true;te^.rev^.al:=true;search(te^.t);list[tot]:=te;dec(tot);end;te:=te^.next;end;end;procedure main;{主过程}var i:longint;begino:=false;for i:=1 to n doif d[i]=0 then dec(bl);{排除孤立点的影响}if bl<>1 then exit;{原图不连通，无解}for i:=1 to n doif odd(d[i]) then exit;{存在奇点，无解}o:=true;for i:=1 to n doif d[i]<>0 then break;tot:=m;search(i);{从一个非孤立点开始寻找欧拉回路}end;procedure print;{输出结果}var i:longint;beginif not o then writeln("No solution.") else beginwriteln(list[1]^.f);for i:=1 to m do writeln(list[i]^.t);end;end;begininit;main;print;end.注意record中的点的排列是输出的倒序，因此，如果要输出欧拉路径，需要将record倒过来输出。求欧拉回路的思路：循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法不保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。具体步骤：1。如果此时与该点无相连的点，那么就加入路径中2。如果该点有相连的点，那么就加入队列之中，遍历这些点，直到没有相连的点。3。处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。4。这个其实是个递归过程。

发布会日日日日日日日日日日日日日日日日

若G是欧拉图，则每个点度数均为偶数。每添加一个环，每个点奇偶度不变。若添加一条边，该边连接两点度数各+1。奇数+1为偶数。现有K个奇度数节点，需使该K个点度数均变为偶，则至少加k/2条边。

不一定,这样的反例有很多：　　对于一个有向图,只要有一个经过所有结点的环路,就成为强连通图.不妨构造一个强连通图,其所有边恰好构成一个环,串联了所有结点；如：a1→a2→a3→……→a1；　　此时,这个图中恰好有一...

#include "SqStack.h" //堆栈的常见操作#include "Queue.h"//队列的常见操作typedef int Graph[200][200];int v,e;void DFS(Graph &G,SqStack &S,int x,int t){int k=0,i,m,a;Push(S,x);for(i=t;i<v;i++)if(G[i][x]>0){k=1;G[i][x]=0; //删除此边G[x][i]=0;DFS(G,S,i,0);break;}//if,forif(k==0){Pop(S);GetTop(S,m);G[x][m]=1;G[m][x]=1;a=x+1;if(StackLength(S)!=e){Pop(S);DFS(G,S,m,a);}//ifelsePush(S,x);}//if}//DFSint BFSTest(Graph G){int a[200],x,i,k=0;LinkQueue Q;InitQueue(Q);EnQueue(Q,0);for(i=0;i<v;i++)a[i]=0;a[0]=1;while(!QueueEmpty(Q)){DeQueue(Q,x);for(i=0;i<v;i++)if(G[x][i]>0)if(a[i]!=1){a[i]=1;EnQueue(Q,i);}//if}//whilefor(i=0;i<v;i++)if(a[i]==0){k=1;break;}if(k==1)return 0;elsereturn 1;}void Euler(Graph &G,int x){int m;SqStack S;InitStack(S);DFS(G,S,x,0);printf("该图的一个欧拉回路为：");while(!StackEmpty(S)){GetTop(S,m);printf("->v%d",m);Pop(S);}//while}void InputM1(Graph &G){int h,z;printf("Please input顶点数和边数 ");scanf("%d",&v);scanf("%d",&e);for(int i=0;i<v;i++)for(int j=0;j<v;j++)G[i][j]=0;printf("please int the邻接矩阵的值(起点(数字)终点(数字))： ");for(int i=0;i<e;i++){scanf("%d",&h);scanf("%d",&z);G[h-1][z-1]=1;G[z-1][h-1]=1;}//for}//InputM1int main(){int i,j,sum,k=0;Graph G;InputM1(G);if(BFSTest(G)==0){printf("该图不是连通图! ");exit(0);}//iffor(i=0;i<v;i++){sum=0;for(j=0;j<v;j++)sum+=G[i][j];if(sum%2==1){k=1;break;}//if}//forif(k==1) printf("该图不存在欧拉回路！ ");elseEuler(G,0);return 1;}

这是一个无解问题

无向图G存在欧拉回路，当且仅当G连通且该图所有顶点度数都是偶数。

srdfsdfvsdv

欧拉路径和欧拉回路判断方法如下：1、欧拉路径。无向图判断法，图连通，有且仅有两个奇点，一个点为起点，另一个点为终点；有向图判断法，有两个点的入度不等于出度，且其中一个点的入度比出度大1，另一个点的出度比入度大1。2、欧拉回路。无向图判断法，图连通，无奇点；有向图判断法，所有点的入度等于出度。判断图是否连通的方法：无向图用dfs访问，看看点是否全部被访问；有向图先转化为无向图，然后再用dfs判定。判断奇点数的方法：奇点数若为0则任意指定起点，奇点数若为2则指定起点为奇点。欧拉路径：从图中一个结点出发走出一条道路，每条边恰好经过一次。欧拉回路：从图中任意点出发，每条边恰好经过一次，最终回到起点。欧拉回路是数学家欧拉在研究著名的德国哥尼斯堡（Koenigsberg）七桥问题时发现的。具有欧拉回路的图称“欧拉图”，具有欧拉路径但不具有欧拉回路的图称“半欧拉图”。找出欧拉回路或欧拉路径可采用深度优先搜索。

若图G中存在这样一条路径，使得它恰通过G中每条边一次，则称该路径为欧拉路径。若该路径是一个圈，则称为欧拉回路。 具有欧拉回路的图称为欧拉图。具有欧拉路径但不具有欧拉回路的图称为半欧拉图。 无向图存在欧拉回路的充要条件： 一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。 有向图存在欧拉回路的充要条件： 一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。

欧拉回路不一定是初级回路，需要判定。1、无向图存在欧拉回路的充要条件一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。2、有向图存在欧拉回路的充要条件一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。3、混合图存在欧拉回路条件要判断一个混合图G（V,E）（既有有向边又有无向边）是欧拉图，方法如下：假设有一张图有向图G"，在不论方向的情况下它与G同构。并且G"包含了G的所有有向边。那么如果存在一个图G"使得G"存在欧拉回路，那么G就存在欧拉回路。扩展资料注意record中的点的排列是输出的倒序，因此，如果要输出欧拉路径，需要将record倒过来输出。求欧拉回路的思路：循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法不保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。

第一眼看见，比划一下，就知道，在所有桥都只能走一遍的前提下，不能把这个地方所有的桥都走遍。 也就是说，如果遍历这个图，必须要重复经过某些边。 为了纪念欧拉，在一个图G中包含G的所有结点和边的 回路 称为 欧拉回路 ,包含G的所有结点和边的 路径 称为 欧拉路径 也就是说，如果欧拉路径闭合，就成了欧拉回路 注意 回路 的概念：从v i 到v i 的、长度非0的、不存在 重复边 的路径 所以上文所说的科尼斯堡七桥并不是欧拉回路。 在图G中存在欧拉回路的前提条件为： 关于一个图中是否存在欧拉回路，需要先说明两个概念： 由于欧拉回路的性质：只能经过每条边一次，所以，对于每一个结点，至少需要有 2n 条边连接该结点（n = 0,1,2,...n），n = 0时，G中只含有一个结点v，则称路径(v)是G的欧拉回路。 也就是说，图G中存在欧拉回路的充要条件是G中每个结点都是偶结点。 设图G存在欧拉回路，则回路的起点和终点是同一结点，含有一条出边和一条入边，所以该结点为偶结点，以此类推，每个结点都连接有 2n (n = 0,1,2,...n) 条边。 图G中存在欧拉路径的充要条件和G中存在欧拉回路的充要条件有些相似： 若奇结点的个数为0，则图G中存在欧拉回路，欧拉回路也是欧拉路径的一种。 将两个奇结点相连，可知这是欧拉回路 (v 1 ,v 2 ,v 3 ,v 4 ,v 5 ,v 6 ,v 3 ,v 1 ) 欧拉路径(v 1 ,v 2 ,v 3 ,v 4 ,v 5 ,v 6 ,v 3 ),起点和终点分别是两个奇结点 关于欧拉回路和欧拉路径的介绍就到此了，谢谢大家！

无向图欧拉回路解法求欧拉回路的一种解法下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路。C语言代码，不全，请不要直接粘贴。 intnum=0;//标记输出队列intmatch[MAX];//标志节点的度，无向图，不区分入度和出度voidsolve(intx){if(match[x]==0)Record[num++]=x;else{for(intk=0;k<=500;k++){if(Array[x][k]!=0){Array[x][k]--;Array[k][x]--;match[x]--;match[k]--;solve(k);}}Record[num++]=x;}}pascal代码:求无向图的欧拉回路（递归实现） programeuler;constmaxn=10000;{顶点数上限}maxm=100000;{边数上限}typetnode=^tr;tr=recordf,t:longint;{边的起始点和终止点}al:boolean;{访问标记}rev,next:tnode;{反向边和邻接表中的下一条边}end;varn,m,bl:longint;{顶点数，边数，基图的极大连通子图个数}tot:longint;g:array[1..maxn]oftnode;d:array[1..maxn]oflongint;{顶点的度}fa,rank:array[1..maxn]oflongint;{并查集中元素父结点和启发函数值}list:array[1..maxm]oftnode;{最终找到的欧拉回路}o:boolean;{原图中是否存在欧拉回路}procedurebuild(ta,tb:longint);{在邻接表中建立边(ta,tb)}vart1,t2:tnode;begint1:=new(tnode);t2:=new(tnode);t1^.f:=ta;t1^.t:=tb;t1^.al:=false;t1^.rev:=t2;t1^.next:=g[ta];g[ta]:=t1;t2^.f:=tb;t2^.t:=ta;t2^.al:=false;t2^.rev:=t1;t2^.next:=g[tb];g[tb]:=t2;end;proceduremerge(a,b:longint);{在并查集中将a,b两元素合并}varoa,ob:longint;beginoa:=a;whilefa[a]<>adoa:=fa[a];fa[oa]:=a;ob:=b;whilefa[b]<>bdob:=fa[b];fa[ob]:=b;ifa<>bthenbegindec(bl);{合并后，基图的极大连通子图个数减少1}ifrank[a]=rank[b]theninc(rank[a]);ifrank[a]>rank[b]thenfa[b]:=aelsefa[a]:=b;end;end;procedureinit;{初始化}vari,ta,tb:longint;beginfillchar(fa,sizeof(fa),0);fillchar(rank,sizeof(rank),0);fillchar(d,sizeof(d),0);readln(n,m);fori:=1tondofa[i]:=i;bl:=n;fori:=1tomdobeginreadln(ta,tb);build(ta,tb);inc(d[tb]);inc(d[ta]);merge(ta,tb);end;end;proceduresearch(i:longint);{以i为出发点寻找欧拉回路}varte:tnode;beginte:=g[i];whilete<>nildobeginifnotte^.althenbeginte^.al:=true;te^.rev^.al:=true;search(te^.t);list[tot]:=te;dec(tot);end;te:=te^.next;end;end;proceduremain;{主过程}vari:longint;begino:=false;fori:=1tondoifd[i]=0thendec(bl);{排除孤立点的影响}ifbl<>1thenexit;{原图不连通，无解}fori:=1tondoifodd(d[i])thenexit;{存在奇点，无解}o:=true;fori:=1tondoifd[i]<>0thenbreak;tot:=m;search(i);{从一个非孤立点开始寻找欧拉回路}end;procedureprint;{输出结果}vari:longint;beginifnotothenwriteln("Nosolution.")elsebeginwriteln(list[1]^.f);fori:=1tomdowriteln(list[i]^.t);end;end;begininit;main;print;end.注意record中的点的排列是输出的倒序，因此，如果要输出欧拉路径，需要将record倒过来输出。求欧拉回路的思路：循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法不保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。具体步骤：1。如果此时与该点无相连的点，那么就加入路径中2。如果该点有相连的点，那么就加入队列之中，遍历这些点，直到没有相连的点。3。处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。4。这个其实是个递归过程。

图G的一个回路,若它恰通过G中每条边一次,则称该回路为欧拉(Euler)回路. 具有欧拉回路的图称为欧拉图（简称E图）. 无向图存在欧拉回路的充要条件 一个无向图存在欧拉回路,当且仅当该图所有顶点度数都是偶数且该图是连通图. 有向图存在欧拉回路的充要条件 一个有向图存在欧拉回路,所有顶点的入度等于出度且该图是连通图,或者 一个顶点的度数为1,另一个度数为-1,其他顶点的度数为0. 混合图存在欧拉回路条件 要判断一个混合图G（V,E）（既有有向边又有无向边）是欧拉图,方法如下： 假设有一张图有向图G",在不论方向的情况下它与G同构.并且G"包含了G的所有有向边.那么如果存在一个图G"使得G"存在欧拉回路,那么G就存在欧拉回路. 其思路就将混合图转换成有向图判断.实现的时候,我们使用网络流的模型.现任意构造一个G".用Ii表示第i个点的入度,Oi表示第i个点的出度.如果存在一个点k,|Ok-Ik|mod 2=1,那么G不存在欧拉回路.接下来则对于所有Ii>Oi的点从源点连到i一条容量为(Ii-Oi)/2的边,对于所有Ii<oi的点从i连到汇点一条容量为(oi-ii) 2,那么就存在欧拉回路. 编辑本段解法 无向图欧拉回路解法 求欧拉回路的一种解法 下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路. C语言代码,不全,请不要直接粘贴. int num = 0;//标记输出队列 int match[MAX];//标志节点的度,无向图,不区分入度和出度 void solve(int x) { if(match[x] == 0) Record[num++] = x; else { for(int k =0;k<=500;k++) { if(Array[x][k] !=0 ) { Array[x][k]--; Array[k][x]--; match[x]--; match[k]--; solve(k); } } Record[num++] = x; } } pascal代码: 求无向图的欧拉回路（递归实现） program euler; const maxn=10000;{顶点数上限} maxm=100000;{边数上限} type tnode=^tr; tr=record f,t:longint;{边的起始点和终止点} al:boolean;{访问标记} rev,next:tnode;{反向边和邻接表中的下一条边} end; var n,m,bl:longint;{顶点数,边数,基图的极大连通子图个数} tot:longint; g:array[1..maxn] of tnode; d:array[1..maxn] of longint;{顶点的度} fa,rank:array[1..maxn] of longint;{并查集中元素父结点和启发函数值} list:array[1..maxm] of tnode;{最终找到的欧拉回路} o:boolean;{原图中是否存在欧拉回路} procedure build(ta,tb:longint);{在邻接表中建立边(ta, tb)} var t1,t2:tnode; begin t1:=new(tnode); t2:=new(tnode); t1^.f:=ta; t1^.t:=tb; t1^.al:=false; t1^.rev:=t2; t1^.next:=g[ta]; g[ta]:=t1; t2^.f:=tb; t2^.t:=ta; t2^.al:=false; t2^.rev:=t1; t2^.next:=g[tb]; g[tb]:=t2; end; procedure merge(a,b:longint);{在并查集中将a, b两元素合并} var oa,ob:longint; begin oa:=a; while fa[a]>a do a:=fa[a]; fa[oa]:=a; ob:=b; while fa[b]>b do b:=fa[b]; fa[ob]:=b; if a>b then begin dec(bl);{合并后,基图的极大连通子图个数减少1} if rank[a]=rank[b] then inc(rank[a]); if rank[a]>rank[b] then fa[b]:=a else fa[a]:=b; end; end; procedure init;{初始化} var i,ta,tb:longint; begin fillchar(fa,sizeof(fa),0); fillchar(rank,sizeof(rank),0); fillchar(d,sizeof(d),0); readln(n,m); for i:=1 to n do fa[i]:=i; bl:=n; for i:=1 to m do begin readln(ta,tb); build(ta,tb); inc(d[tb]); inc(d[ta]); merge(ta,tb); end; end; procedure search(i:longint);{以i为出发点寻找欧拉回路} var te:tnode; begin te:=g[i]; while te>nil do begin if not te^.al then begin te^.al:=true; te^.rev^.al:=true; search(te^.t); list[tot]:=te; dec(tot); end; te:=te^.next; end; end; procedure main;{主过程} var i:longint; begin o:=false; for i:=1 to n do if d[i]=0 then dec(bl);{排除孤立点的影响} if bl>1 then exit;{原图不连通,无解} for i:=1 to n do if odd(d[i]) then exit;{存在奇点,无解} o:=true; for i:=1 to n do if d[i]>0 then break; tot:=m; search(i);{从一个非孤立点开始寻找欧拉回路} end; procedure print;{输出结果} var i:longint; begin if not o then writeln("No solution.") else begin writeln(list[1]^.f); for i:=1 to m do writeln(list[i]^.t); end; end; begin init; main; print; end. 注意record中的点的排列是输出的倒序,因此,如果要输出欧拉路径,需要将record倒过来输出. 求欧拉回路的思路： 循环的找到出发点.从某个节点开始,然后查出一个从这个出发回到这个点的环路径.这种方法不保证每个边都被遍历.如果有某个点的边没有被遍历就让这个点为起点,这条边为起始边,把它和当前的环衔接上.这样直至所有的边都被遍历.这样,整个图就被连接到一起了. 具体步骤： 1.如果此时与该点无相连的点,那么就加入路径中 2.如果该点有相连的点,那么就加入队列之中,遍历这些点,直到没有相连的点. 3.处理当前的点,删除走过的这条边,并在其相邻的点上进行同样的操作,并把删除的点加入到路径中去. 4.这个其实是个递归过程.

欧拉回路是必须经过所有节点。根据查询相关资料信息显示，欧拉回路需要经过每个节点，并且需要记录每个节点的度数，依次来判断是否存在欧拉回路。欧拉回路是指若图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Eulerpath)。

欧拉路径包括欧拉路（不形成回路）和欧拉回路两种情况。连通无向图，当有零个奇数度节点，即没有奇数度节点，此时所有节点度数都是偶数，一定有欧拉回路。具有欧拉回路的图称为欧拉图。连通无向图，当只有两个奇数度节点，其他节点度数都为偶数时，一定有欧拉路。

欧拉回路是经过所有边一次然后回到原点，哈密顿是经过所有节点一次然后回到原点，tsp问题就是哈密顿回路

图 G 的一个回路,若它通过 G 中每条边一次且仅一次,则称为欧拉回路。而具有这种回路的图称为欧拉图(简称 E 图).或者：一副图，寻找一条只通过每条边一次的路径叫做欧拉路径．如果这条路径的起点和终点是同一点，那么这条路径叫做欧拉回路．有关的问题即是欧拉回路问题，建议参考哥尼斯堡七桥问题或一笔画问题。欧拉回路的判定规则：1.如果通奇数桥的地方多于两个，则不存在欧拉回路；2.如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；3.如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。

一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图可以用邻接矩阵或者邻接表，做一次DFS或者BFS访问各个节点判断入度出度就行

if (){ mov ax, 10 mov bx, 0 mov cx, 0 mov dx, 0 add bx, ax add cx, bx add dx, cx loop if}

先设置一个判断迷宫能否被破坏的过程或函数，再用广搜对每一个位置的一切可能性进行试验，每试一次就判断一次，如果条件成立，就保存这一种方法的能量耗损和破坏的路径，每个位置的每一个可能性都检查完后，找出最佳方案

我只知道欧拉图这是数学家欧拉提出的.用几个圆圈表示几个概念的外延关系.下面是一个欧拉图，图片点击可以放大