算法欧拉回路

① 图论中，求欧拉路径的算法有哪些

首先要根据欧拉路径的存在条件来判断一个图是否存在欧拉路径,判断条件为如下3条
对于一个无向图，如果它每个点的度都是偶数，那么它存在一条欧拉回路；
如果有且仅有2个点的度为奇数，那么它存在一条欧拉路；
如果超过2个点的度为奇数，那么它就不存在欧拉路了。
然后可以用Fleury算法求欧拉路径,可以参照
http://www.cnblogs.com/Lyush/archive/2013/04/22/3036659.html

② 欧拉回路matlab算法实现

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

③ ACM需要那些方面的知识

备战ACM资料
一：知识点
数据结构：
1，单，双链表及循环链表
2，树的表示与存储，二叉树（概念，遍历）二叉树的
应用（二叉排序树，判定树，博弈树，解答树等）
3，文件操作（从文本文件中读入数据并输出到文本文
件中）
4，图（基本概念，存储结构，图的运算）
数学知识
1，离散数学知识的应用（如排仿岩乎列组合、简单的图论，数
理逻辑）
2，数论知识
3，线性代数
4，组合代数
5，计算几何
二 算法
1，排序算法（冒抛法，插入排序，合并排序，快速排
序，堆排序）
2，查找（顺序查找，二分发）
3，回溯算法
4，递归算法
5，分治算法
6，模拟法
7，贪心法
8，简单搜索算法（深度优先，广度优先），搜索中的
剪枝，A*算法
9，动态规划的思想及基本算法
10，高精度运算
三、ACM竞赛的题型分析
竞赛的程序设计一般只有16种类型，它们分别是：
Dynamic Programming （动态规划）
Greedy （贪心算法）
Complete Search （穷举搜索）
Flood Fill （不知该如何翻译）
Shortest Path （最短路径）
Recursive Search Techniques （回溯搜索技术）
Minimum Spanning Tree （最小生成树）
Knapsack （背包问题）
Computational Geometry (计算几何学)
Network Flow （网络流）
Eulerian Path （欧拉回路）
Two-Dimensional Convex Hull （不知如何翻译）
BigNums （大数问题）
Heuristic Search （启发式搜索）
Approximate Search （近似搜索）
Ad Hoc Problems （杂题）
四 ACM竞赛参考书
《实用备悉算法的分析与程序设计》 （吴文虎，王建德着，电子工业出版社，竞赛类的黑宝书）
《青少年国际和全国信息学（计算机）奥林枣耐匹克竞赛指导）――组合数学的算法
和程序设计》（吴文虎，王建德着，清华大学出版社，参加竞赛组合数学必学）
《计算机算法设计与分析》 （王晓东编着，最好的数据结构教材）
《数据结构与算法》 （傅清祥，王晓东编着，我所见过的最好的算法教材）
《信息学奥林匹克竞赛指导――1997-1998竞赛试题解析》（吴文虎，王建德着，清华大学出版社）
《计算机程序设计技巧》 D.E.Kruth着，算法书中最着名的《葵花宝典》，大师的作品，难度大）
《计算几何》周陪德着
《ACM国际大学生程序设计竞赛试题与解析（一）》 （吴文虎着，清华大学出版社）
《数学建模竞赛培训教材》 共三本 叶其孝主编
《数学模型》 第二版 姜启源
《随机规划》
《模糊数学》
《数学建模入门》 徐全智
《计算机算法设计与分析》 国防科大
五 常见的几个网上题库
常用网站：
1）信息学初学者之家：
（2）大榕树编程世界：
（3）中国教育曙光网：
（4）福建信息学奥林匹克：
（5）第20届全国青少年信息学奥林匹克竞赛：
（6）第15届国际青少年信息学奥林匹克竞赛：
（7）全美计算机奥林匹克竞赛：
（8）美国信息学奥林匹克竞赛官方网站：
（9）俄罗斯Ural州立大学：
（10）西班牙Valladolid大学：
（11）ACM-ICPC：
（12）北京大学：
（13）浙江大学：
（14）IOI：
（15）2003年江苏省信息学奥林匹克竞赛夏令营：
（16）
（17）
（18）
（19）
（20） colin_fox/colin_fox
五 如何备战ACM/ICPC
1，个人准备（算法书，习题集，网上做题和讨论）
2，1000题=亚洲冠军=世界决赛
3，做好资料收集和整理工作

④ 求算法：欧拉路

欧拉回路 【定义】
图G的一个回路，若它恰通过G中每条边一次,则称该回路为欧拉(Euler)回路。
具有欧拉回路的图称为欧拉图（简称E图）。
【相关结论】
定理：
一个无向图是欧拉图，当且仅当该图所有顶点度数都是偶数。
一个有向图是欧拉图，当且仅当该图所有顶点度数都是0。
求欧拉回路的一种解法
下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路。
int num = 0;//标记输出队列
int match[MAX];//标志节点的度，无向图，不区分入度和出度
void solve(int x)
l{
l if(match[x] == 0)
l
l Record[num++] = x;
l
l else
l {
l for(int k =0;k<=500;k++)
l {
l if(Array[x][k] !=0 )
l {
l Array[x][k]--;
l Array[k][x]--;
l match[x]--;
l match[k]--;
l solve(k);
l }
l
l }
l Record[num++] = x;
l }
l}
注意record中的点的排列是输出的到序，因此，如果要输出欧拉路径，需要将record倒过来输出。
求欧拉回路的思路：
循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。
具体步骤：
1。如果此时与该点无相连的点，那么就加入路径中
2。如果该点有相连的点，那么就列一张表，遍历这些点，直到没有相连的点。
3。处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。
4。这个其实是个递归过程。

--以上为网络的内容

⑤ 概要描述一个算法，判断一个用邻接矩阵表示的连通图是否具有欧拉回路。该算法效率类型如何

算法如下：
设邻接矩阵维度为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)的吧

⑥ 七桥问题能用递归算法解决计算问题吗

七桥问题可以使用递归算法进行计算塌巧闷

在七桥问题中，可以使用递归算法来遍历所宽拆有可能的路径，并检查是否存在一条路径可以穿过所有的桥，也就是欧拉回路。递归算法可以按照以下步骤进行：

• 从一个起点开始遍历，找到所有与该点相邻的点。

• 对于每个相邻的点，尝试通过与它相连的桥移动到该团弯点，并将该点标记为已访问。

• 重复第1和第2步，直到没有未访问的点可用。

• 如果已经访问了所有的点并且路径中每个桥都只被经过一次，那么就找到了欧拉回路，返回True；否则返回False。

⑦ 急求c++fleury算法欧拉回路代码

1#include <stdio.h>
2#include <string.h>
3
4
5struct stack
6{int top , node[210];} f; //顶点的堆栈
7
8int a[201][201]; //图的邻接矩阵
9
10int n;
11
12void dfs(int x) //图的深度优先遍历
13{
14int i;
15
16f.top ++; f.node[f.top] = x;
17
18for (i = 1; i <= n; i ++)
19
20 if (a[i][x] > 0)
21 {
22 a[i][x] = 0; a[x][i] = 0; //删除此边
23
24 dfs(i);
25
26 break;
27 }
28}
29
30void Euler(int x) //欧拉路算法
31{
32int i , b;
33
34f.top = 0; f.node[f.top] = x; //入栈
35
36while (f.top >= 0)
37{
38 b = 0;
39
40 for (i = 1; i <= n; i ++)
41 if (a[f.node[f.top]][i] > 0)
42 {b = 1; break;}
43
44 if (b == 0) //如果没有点可以扩展，输出并出栈
45 {
46 printf("%d " , f.node[f.top]);
47
48 f.top --;
49 }
50 else {f.top --; dfs(f.node[f.top+1]);} //如果有，就DFS
51 }
52}
53
54int main()
55{
56
57int m , s , t , num , i , j , start;
58
59 //input
60
61 scanf("%d %d" , &n , &m); //n顶点数 m边数
62
63 memset(a , 0 , sizeof(a));
64
65 for (i = 0; i < m; i ++)
66 {
67 scanf("%d %d" , &s , &t);
68 a[s][t] = 1; a[t][s] = 1;
69 }
70
71
72 //判断是否存在欧拉回路
73
74 s = 0; start = 1;
75
76 for (i = 1; i <= n; i ++)
77 {
78 num = 0;
79
80 for (j = 1; j <= n; j ++)
81 num += a[i][j];
82
83 if (num % 2 == 1)
84{start = i; s ++;}
85 }
86
87 if ((s == 0) || (s == 2))
88Euler(start);
89 else printf("No Euler path\n");
90
91 getchar(); getchar();
92 return 0;
93}
94

⑧ 求NOIP提高组考试需掌握的算法（大纲）

1、排序算法（快排、选择、冒泡、堆排序、二叉排序树、桶排序）
2、DFS/BFS 也就是搜索算法，谨含乎剪枝务必要学！ 学宽搜的时候学一下哈希表!
3、树
①遍历
②二叉树
③二叉排序树（查找、生成、删除）
④堆（二叉堆、左偏树、堆排序）
⑤Trie树祥悉
4、图（图论建模）
①最小生成老弯树
②最短路径
③计算图的传递闭包
④连通分量（其中要掌握并查集技术）
强连通分量tarjin
⑤拓扑排序、关键路径
⑥哈密尔顿环
⑦欧拉回路（USACO 3.3 题1 Fence）
⑧Bell-man Ford、SPFA（能解决负权回路）（USACO 3.2 题6 Butter）
⑨二分图（匈牙利算法）(USACO 4.2 题2 stall)
5、动态规划（背包问题只是其中一种）
①线性动规
②区间动规
③树形动规
④图形动规
6、分治（掌握了动规分治就好学了）
7、贪心
8、位运算（可以用来进行优化）

⑨ 求大神回答，用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;
}

⑩ NOI考试的内容是什么

1 时间复杂度（渐近时间复杂隐塌让度的严格定义，NP问题，时间复杂度的分析方法，主定理）
2 排序算法（平方排序算法的应用，Shell排序，快速排序，归并排序，时间复杂度下界，三种线性时间排序，外部排序）
3 数论（整除，集合论，关系，素数，进位制，辗转相除，扩展的辗转相除，同余运算，解线性同余方程，中国剩余定理）
4 指针（链表，搜索判重，邻接表，开散列，二叉树的表示灶局，多叉树的表示）
5 按位运算（and，or，xor，shl，shr，一些应用）
6 图论（图论模型的建立，平面图，欧拉公式与五色定理，求强连通分量，求割点和桥，欧拉回路，AOV问题，AOE问题，最小生成树的三种算法，最短路的三种算 法，标号法，差分约束系统，验证二分图衫哗，Konig定理，匈牙利算法，KM算法，稳定婚姻系统，最大流算法，最小割最大流定理，最小费用最大流算法）
7 计算几何（平面解几及其应用，向量，点积及其应用，叉积及其应用，半平面相交，求点集的凸包，最近点对问题，凸多边形的交，离散化与扫描）
8 数据结构（广度优先搜索，验证括号匹配，表达式计算，递归的编译，Hash表，分段Hash，并查集，Tarjan算法，二叉堆，左偏树，斜堆，二项堆，二叉查找树，AVL，Treap，Splay，静态二叉查找树，2-d树，线段树，二维线段树，矩形树，Trie树，块状链表）
9 组合数学（排列与组合，鸽笼原理，容斥原理，递推，Fibonacci数列，Catalan数列，Stirling数，差分序列，生成函数，置换，Polya原理）
10 概率论（简单概率，条件概率，Bayes定理，期望值）
11 矩阵（矩阵的概念和运算，二分求解线性递推方程，多米诺骨牌棋盘覆盖方案数，高斯消元）
12 字符串处理（KMP，后缀树，有限状态自动机，Huffman编码，简单密码学）
13 动态规划（单调队列，凸完全单调性，树型动规，多叉转二叉，状态压缩类动规，四边形不等式）
14 博奕论（Nim取子游戏，博弈树，Shannon开关游戏）
15 搜索（A*，ID，IDA*，随机调整，遗传算法）
16 微积分初步（极限思想，导数，积分，定积分，立体解析几何）