演算法歐拉迴路

① 圖論中，求歐拉路徑的演算法有哪些

首先要根據歐拉路徑的存在條件來判斷一個圖是否存在歐拉路徑,判斷條件為如下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 微積分初步（極限思想，導數，積分，定積分，立體解析幾何）