欧拉回路与欧拉道路
欧拉回路与欧拉道路
图G的一条回路，如果恰好经过图G中的每一条边一次，则称这样的回路由为欧拉（Euler）回路。
当且仅当一个图能够遍历所有节点而不重复时，则称其为欧拉道路。
被称为包含欧拉图（简称E图）的那些具有欧拉回路或欧拉道路的图形
有向图的欧拉回路
一个有向图若存在欧拉回路，则必须满足它是连通图这一必要条件之外还需要满足其他条件即每个顶点的入次数与其出次数相等或者存在两个特定顶点使得其中一个顶点的出次数比其入次数多1而另一个顶点则相反其入次数比出次数多1这样的情况下则必定存在一条欧拉回路
当其每个节点的入度过等于出度过时，则可以从任一顶点出发并行遍每条边一次并最终返回起点即形成一个欧拉回路；而在另一种情形下则需从一个出度过比入度过高一的顶点出发最终到达一个入度过比出度过高一的顶点从而构成一条开放式的欧拉路径
无向图的欧拉回路
与有向图相同，在无向图中也需满足以下条件：首先必须是连通的；其次如果最多仅有两个奇度顶点，则该图即可满足存在欧拉回路或欧拉路径。具体而言，在存在奇度顶点的情况下（即有两个），可以从任选的一个奇度顶点出发构造一条包含所有边的路径；否则（即不存在奇度顶点时），可以从任何一个顶点出发构造出一个完整的回路。（注意：百度百科上的描述不正确）
**
**
如果只是判断一个图是否能够形成欧拉回路的话，就用上面的思路：
首先根据出度跟入度的关系，判断是否满足要求
然后用判定图的连通性可采用并查集方法或深度优先搜索（Dfs）。若需获取路径信息则可运用深度优先搜索（Dfs）算法。
**
**
要是需要求出欧拉路径，就用下面这个函数。
此程序是用来寻找图中的欧拉回路或欧拉路径的一种实现方式。若需获取欧拉路径，则需在主程序中调用该函数，并注意以下几点：首先函数参数指定起点即为此条路径的一端；此外需要注意的是输出结果顺序相反因此，在使用的时候应采取相应的措施以确保正确性——应将结果按顺序存入栈中以便后续处理。此外该方法适用于无向图和有向图的遍历问题。实际上该算法与Prim算法类似其中后者是一个更为复杂的优化版本——前者仅用于寻找特定类型的路径而后者则更注重全局最优解
void euler(int u)
{
for(int v=0;v<n;v++)
{
if(map[u][v] && !vis[u][v])
{
vis[u][v] = vis[v][u] = 1;//如果是有向图的只需判断一个
euler(v);
printf("%d %d\n",u,v);
}
}
}该问题涉及一个由珠子制成的链子及其相关的算法挑战
具体来说
此题题意较为直观。一条链断裂后，在其上各节点均有两个赋值。将所有珠子串联起来，则相邻两节点的赋值必须相等方能实现连接。值得注意的是第二组测试数据表现优异。由此可推断问题可建模为无向图：首先需检验图中各节点度数均为偶数（这是因为问题构成的是一个回路而非路径）。然后利用上述欧拉代码进行遍历即可完成求解。
#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;
stack <E> st;
void euler( int u )
{
for ( int v = 1; v < n; ++v ) if ( map[u][v] )
{
map[u][v]--; map[v][u] = map[u][v];
euler( v );
tmp.u = u, tmp.v = v;
st.push(tmp);
}
}
int main()
{
int n,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));
//memset(out,0,sizeof(out));
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);
while ( !st.empty() ) {
tmp = st.top(); st.pop();
printf("%d %d\n", tmp.u, tmp.v);
}
}
printf("\n");
}
return 0;
}UVA10129 - Play on Words 这道题题意是给出n个单词，让每个点此的首字母指向未字母形成连通，这样形成一个有向图，求这个有向图的欧拉回路。
核心思路是：第一步是对图进行读取；第二步是通过计算节点的出度和入度来判断是否满足特定条件；最后使用深度优先搜索（Dfs）的方法来确定图的连通性。
#include<stdio.h>
#include<string.h>
#include<math.h>
int visit[26],a[26][26];
void dfs(int x)
{
int i;
visit[x]=0;
for (i=0;i<26;i++)
if ((visit[i]==1)&&(a[x][i]==1)) dfs(i);
}
int main()
{
int f,t,k1,k2,num,n,i,j,l,in[26],out[26];
char s[1010];
scanf("%d",&t);
while (t--)
{
memset(a,0,sizeof(a));
for (i=0;i<26;i++)
{in[i]=0; out[i]=0; visit[i]=0;}
scanf("%d\n",&n);
while (n--)
{
gets(s); l=strlen(s);
k1=s[0]-'a'; k2=s[l-1]-'a';
++in[k1]; ++out[k2];
visit[k1]=1; visit[k2]=1;
a[k1][k2]=1;
num=k1;
}
for (i=0;i<26;i++)
in[i]=in[i]-out[i];
f=0; k1=0; k2=0;
for (i=0;i<26;i++)
{
if (in[i]==-1) ++k1;
else if (in[i]==1) {++k2;num=i;} //因为是有向图，如果不是欧拉回路的情况，随便找个点为起点dfs不一定能遍历所有点，如3 a b b c c d只能以a为起点否则就会判断连通性错误
else if (in[i]!=0) f=1;
}
if (f==0)
{
if ((k1+k2==0) || ((k1==1)&&(k2==1)))
{
dfs(num);
for (i=0;i<26;i++)
f+=visit[i];
}
else f=1;
}
if (f!=0) printf("The door cannot be opened.\n");
else printf("Ordering is possible.\n");
}
return 0;
}**
**