⑴ 如何用c语言或c++判断是否是欧拉回路
一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图
一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图
可以用邻接矩阵或者邻接表，做一次DFS或者BFS访问各个节点判断入度出度就行
⑵ 概要描述一个算法，判断一个用邻接矩阵表示的连通图是否具有欧拉回路。该算法效率类型如何
算法如下：
设邻接矩阵维度为n*n，将邻接矩阵进行标准化转为概率转移矩阵，方法是每一行元素除以行和保证每行和为1（由于连通，每行和一定大于零，所以除法可实现）
首先判断矩阵对角线上是否有>0的元素，如有证明有欧拉回路（自环），否则进行下一步
第二步将矩阵平方，判断矩阵对角线上是否有>0的元素，如有证明有欧拉回路（两个节点的环），否则进行下一步
以此类推，直到计算矩阵的n次方，判断对角线上是否有>0的元素，如有证明有欧拉回路，此时仍没有>0的元素证明该连通图没有欧拉回路
这个方法的依据是，如果将邻接矩阵标准化为概率转移矩阵，那么对矩阵进行k次方，得到的矩阵第(i,j)个元素的意义就是通过k步使得从i走到j的概率，那么对角线(i,i)代表的就是从i经k步回到i的概率，这个概率大于零就代表有一条回路。对于一个共有n个节点的有欧拉回路的连通图，最短的欧拉回路结点个数一定小于等于n，所以如果n次方后还没有出现回路概率就可以判断没有回路了
算法效率类型我不太清楚是怎么算的……不过这个算法方面，标准化矩阵的部分运算复杂度不超过n，之后至多进行n步，每一步的矩阵幂大概可以到O(n)复杂度，判断至多也就是O(n)，所以这个复杂度不超过O(n^2)的吧
⑶ 欧拉回路中，顶点度数到底是什么
图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=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;{原图中是否存在欧拉回路}
procere 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;
procere 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;
procere 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;
procere 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;
procere 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;
procere 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。这个其实是个递归过程。
⑷ 用C语言编程判断一个无向图是不是欧拉图
一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数，且该图是连通图。
一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。
可以用邻接矩阵或者邻接表，做一次DFS或者BFS访问各个节点判断入度出度就行。
(4)判断图是否存在欧拉回路c语言扩展阅读：
1、无向连通图 G 是欧拉图，当且仅当 G 不含奇数度结点( G 的所有结点度数为偶数)；
2、无向连通图G 含有欧拉通路，当且仅当 G 有零个或两个奇数度的结点；
3、有向连通图 D 是欧拉图，当且仅当该图为连通图且 D 中每个结点的入度=出度；
⑸ C语言编程判断哥尼斯堡7桥是否为欧拉图
若是一个一笔画图形，要么只有两个奇点，也就是仅有起点和终点，这样一笔画成的图形是开放的；要么没有奇点，也就是终点和起点连接起来，这样一笔画成的图形是封闭的。由于七桥问题有四个奇点，所以要找到一条经过七座桥，但每座桥只走一次的路线是不可能的
⑹ 图论中，求欧拉路径的算法有哪些
首先要根据欧拉路径的存在条件来判断一个图是否存在欧拉路径,判断条件为如下3条
对于一个无向图，如果它每个点的度都是偶数，那么它存在一条欧拉回路；
如果有且仅有2个点的度为奇数，那么它存在一条欧拉路；
如果超过2个点的度为奇数，那么它就不存在欧拉路了。
然后可以用Fleury算法求欧拉路径,可以参照
http://www.cnblogs.com/Lyush/archive/2013/04/22/3036659.html
⑺ 欧拉回路的解法
无向图欧拉回路解法
求欧拉回路的一种解法
下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路。
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;{原图中是否存在欧拉回路}procerebuild(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;proceremerge(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;procereinit;{初始化}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;proceresearch(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;proceremain;{主过程}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;procereprint;{输出结果}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（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语言实现离散数学中的Fleury算法，最后结果要求1、判断是否为欧拉图；2、输出欧拉回路
#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,for
if(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);
}//if
else
Push(S,x);
}//if
}//DFS
int 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
}//while
for(i=0;i<v;i++)
if(a[i]==0)
{
k=1;
break;
}
if(k==1)
return 0;
else
return 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
顶点数和边数
\n");
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
邻接矩阵的值
(
起点
(
数字
)
终点
(
数字
))
：
\n");
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
}//InputM1
int main()
{
int i,j,sum,k=0;
Graph G;
InputM1(G);
if(BFSTest(G)==0)
{
printf("
该图不是连通图
!\n");
exit(0);
}//if
for(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
}//for
if(k==1) printf("
该图不存在欧拉回路！
\n");
else
Euler(G,0);
return 1;
}