遍歷所有元素的演算法

㈠ 求高手給個遍歷演算法

圖的遍歷

從圖中某一頂點出發訪遍圖中其餘頂點，且使每一頂點僅被訪問一次。這一過程叫做圖的遍歷。
遍歷圖的基本方法有兩種：深度優先搜索和廣度優先搜索。這兩種方法都適用於有向圖和無向圖。
和樹的遍歷類似，圖的遍歷也是從某個頂點出發，沿著，某條邊搜索路徑對圖中所有頂點各作一次訪問。若給定的圖是連通圖，則從圖中任意頂點出發順著邊可以訪問到該圖中所有的頂點，然而，圖的遍歷比樹的遍歷復雜得多，這是因為圖中的任一點都可能和其餘頂點相鄰接，故在訪問了某個頂點之後，可能順著某條迴路又到了該頂點。為了避免重復訪問同一個頂點，必須記住每個頂點是否被訪問過。為此，可設置一個布爾向量visited[1..n],它的初值為false，一旦訪問了頂點vi，便將visited[i]置為ture。

一、連通圖的深度優先搜索
連通圖深度優先搜索的基本思想如下：假定圖中某個頂點v1為出發點，首先訪問出發點v1，然後任選一個v1的訪問過的鄰接點v2，以v2為新的出發點繼續進行深度優先搜索，直至圖中所有頂點被訪問過。
顯然，圖的深度優先搜索是一個遞歸過程，類似於樹的前序遍歷，它的特點是盡可能先對縱深方向進行搜索，故稱之深度優先搜索。
現以圖5-10中G為例說明深度優搜索過程。假定v1是出發點，首先訪問v1。因v1有兩個鄰接點v2、v3均未被訪問，選擇v2作為新的出發點。訪問v2之後，再找v2的未訪問過的鄰接點。同v2鄰接的有v1、v4、v5，其中v1以被訪問過，而v4、v5未被訪問。選擇v4作為新的出發點。重復上述搜索過程繼續依次訪問v8、v5。訪問v5之後，由於與v5相鄰的頂點均以被訪問，搜索退回到v8。由於v8、v4、v2都沒有未被訪問的鄰接點，所以搜索過程連續地從v8退回到v4，再退回到v2最後退回到v1這時選擇v1的未被訪問過的鄰接點v3，繼續往下搜索，依次訪問v3、v6、v7，從而遍歷了圖中全部頂點。在這個過程中得到的頂點的訪問序列：

(a)無向圖G

(b)G的深度優先搜索過程
圖5-10a 深度優先搜索過程示例

v1→v2→v4→v8→v5→v3→v6→v7
這樣的序列就稱之為圖的深度優先搜索遍歷序列。
連通圖的深度優先搜索的非形式演算法如下:
procere dfs (g:graph;v1:integer);
//從v1出發深度優先遍歷圖g//
begin write(v1);
visited[v1]:=ture;
找出g中v1的第一鄰接點w;
while w存在do
[ if w 未被訪問 then dfs(g,w);
w:=g中v1的下一鄰接點]
end;
上述非行式演算法未涉及圖的存儲結構.圖的遍歷過程必然地包含對圖中每個頂點查找其鄰接點這一操作;而在圖的不同存儲結構上查找鄰接點的方法是不同的.
若以鄰接表為存儲結構,查找鄰接點操作實際上是順序查找鏈表.鄰接表上的深度優先演算法如下:
procere dfs(g:adj_list;v1:integer);
//從v1出發深度優先遍歷圖g.g以鄰接表為存儲結構//
begin write(v1);
visited[v1]:=ture;//標志v1已訪問//
p=g[v1].link;//找v1的第一個鄰接點//
while p<>nil do
[ if not (visited[p↑.adjvex]);//書錯寫成vertex//
then dfs(g,p↑.adjvex);
p:=p↑.next]//回溯----找v1的下一個鄰接點//
end;

二、連通圖的廣度優先搜索
連通圖廣度優先搜索的基本思想是：從圖中某個頂點v1出發，訪問了v1之後依次訪問v1的所有鄰接點；然後分別從這些鄰接點出發按深度優先搜索遍歷圖的其它頂點，直至所有頂點都被訪問到。它類似於樹的按層次遍歷，其特點是盡可能優先對橫向搜索，故稱之為廣度優先搜索。
下面以圖5-10中G為例說明廣度優先搜索的過程。首先從起點v1出發，訪問v1。v1有兩個未曾訪問的鄰接點v2和v3。先訪問v2，再訪問v3。然後再先後訪問v2的未曾訪問過的鄰接點v4、v5及v3的未曾訪問過的鄰接點v6、v7。最後訪問v4的未曾訪問過的鄰接點v8。至此圖中所有頂點均以被訪問到。得到的頂點訪問序列為：

(a)無向圖G

(b)G的廣度優先搜索過程
圖5-10b 廣度優先搜索過程示例

v1→v2→v3→v4→v5→v6→v7→v8
相應的，這樣的序列就稱之為圖的廣度優先搜索遍歷序列。
在廣度優先搜索中，若對x的訪問先於y，則對x鄰接點的訪問也先於隊y的鄰接點的訪問。因此，可採用隊列來暫存那些剛訪問過，但可能還有為訪問過的鄰接點的頂點。
連通圖的廣度優先搜索演算法如下：
procere bfs(g:adj_list;v1:integer);//書錯寫成adjlist//
//以鄰接表為存儲結構的廣度優先搜索。Q為隊列，假定visited的各分量已只置 為false//
begin init_linkedque(Q);//設計一個空隊Q//
visited[v1]:=ture;write(v1);
in_limkedque(Q,v1); //v1入隊//
while not empty(Q) do
[ v:=out_linkedque(Q);
p:=adj_list[v].link;//書錯寫成adjlist//
while p<>nil do
[ if visited[p↑.adjvex]:=false;//書錯寫成vertex//
then
[visited[p↑.adjvex]:=ture;
with(p↑.adjvex);
in_linkedque(Q,p↑.adjvex);]
p:=p↑.next]]
end;

三、圖的連通分量計算
如果要遍歷一個非連通圖，則需要多次調用dfs或bfs，每一次都要得到一個連通分量；調用dfs或bfs的次數就是連通分量的個數。因此很容易寫出非連通圖的遍歷演算法和計算一個圖的連通分量得演算法。下面給出的是以鄰接表為存儲結構，通過調用深度優先搜索演算法實現的計算連通分量的演算法。
procee conn_component (var g:graph;
var visited:array[1..vnum);
begin for v:=1 to vnum do
visited[v]:flase;
count:=0;
for v:=1 to vnum do
if not(visited[v])then
[count:=count+1;
write('component',count,':');
dfs(g,v);writeln;]
end;
對於圖5-5中非連通圖G3，用上述演算法可求出3個連通分量，各連通分量所含頂點如下：
component1: 1 2 3
component2: 4 5 6 7
component3: 8 9
注意，若從上述演算法中刪去有關連通分量計數器的操作，就得到一個非連通圖德遍歷演算法。

詳細資料和圖片請參看參考資料，那裡的比較詳細

㈡ 求二叉樹遍歷演算法C語言實現的

Status
PreOrderTraverse
(
BiTree
T,
Status
(
*Visit
)
(
TElemType
e
)
)
{
//
採用二叉鏈表存儲結構，Visit
是對數據元素操作的應用函數，先序遍歷二叉樹
T
的遞歸演算法。
if
(
T
)
{
//
若
T
不為空
if
(
Visit
(
T->data
)
)
//
調用函數
Visit
if
(
PreOrderTraverse
(
T->lchild,
Visit
)
)
//
遞歸調用左子樹
if
(
PreOrderTraverse
(
T->rchild,
Visit
)
)
return
OK;
//
遞歸調用右子樹
return
ERROR;
}
else
return
OK;
}
//
PreOrderTraverse

㈢ 圖遍歷的演算法

圖的遍歷方法目前有深度優先搜索法和廣度（寬度）優先搜索法兩種演算法。 深度優先搜索法是樹的先根遍歷的推廣，它的基本思想是：從圖G的某個頂點v0出發，訪問v0，然後選擇一個與v0相鄰且沒被訪問過的頂點vi訪問，再從vi出發選擇一個與vi相鄰且未被訪問的頂點vj進行訪問，依次繼續。如果當前被訪問過的頂點的所有鄰接頂點都已被訪問，則退回到已被訪問的頂點序列中最後一個擁有未被訪問的相鄰頂點的頂點w，從w出發按同樣的方法向前遍歷，直到圖中所有頂點都被訪問。其遞歸演算法如下：
Boolean visited[MAX_VERTEX_NUM]; //訪問標志數組
Status (*VisitFunc)(int v); //VisitFunc是訪問函數，對圖的每個頂點調用該函數
void DFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum; ++v)
visited[v] = FALSE; //訪問標志數組初始化
for(v=0; v<G.vexnum; ++v)
if(!visited[v])
DFS(G, v); //對尚未訪問的頂點調用DFS
}
void DFS(Graph G, int v){ //從第v個頂點出發遞歸地深度優先遍歷圖G
visited[v]=TRUE; VisitFunc(v); //訪問第v個頂點
for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))
//FirstAdjVex返回v的第一個鄰接頂點，若頂點在G中沒有鄰接頂點，則返回空（0）。
//若w是v的鄰接頂點，NextAdjVex返回v的（相對於w的）下一個鄰接頂點。
//若w是v的最後一個鄰接點，則返回空（0）。
if(!visited[w])
DFS(G, w); //對v的尚未訪問的鄰接頂點w調用DFS
} 圖的廣度優先搜索是樹的按層次遍歷的推廣，它的基本思想是：首先訪問初始點vi，並將其標記為已訪問過，接著訪問vi的所有未被訪問過的鄰接點vi1,vi2,…, vi t，並均標記已訪問過，然後再按照vi1,vi2,…, vi t的次序，訪問每一個頂點的所有未被訪問過的鄰接點，並均標記為已訪問過，依次類推，直到圖中所有和初始點vi有路徑相通的頂點都被訪問過為止。其非遞歸演算法如下：
Boolean visited[MAX_VERTEX_NUM]; //訪問標志數組
Status (*VisitFunc)(int v); //VisitFunc是訪問函數，對圖的每個頂點調用該函數
void BFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum, ++v)
visited[v] = FALSE;
initQueue(Q); //置空輔助隊列Q
for(v=0; v<G.vexnum; ++v)
if(!visited[v]){
visited[v]=TRUE; VisitFunc(v);
EnQueue(Q, v); //v入隊列
while(!QueueEmpty(Q)){
DeQueue(Q, u); //隊頭元素出隊並置為u
for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
if(!Visited[w]){ //w為u的尚未訪問的鄰接頂點
Visited[w]=TRUE; VisitFunc(w);
EnQueue(Q, w);
}
}
}
}

㈣ python使用冒泡排序

冒泡排序（Bubble Sort）也是一種簡單直觀的排序演算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢"浮"到數列的頂端。
def bubbleSort(arr):
n = len(arr)

# 遍歷所有數組元素
for i in range(n):

# Last i elements are already in place
for j in range(0, n-i-1):

if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]

arr = [64, 34, 25, 12, 22, 11, 90]

bubbleSort(arr)

print ("排序後的數組:")
for i in range(len(arr)):
print ("%d" %arr[i])

㈤ 如何從左到右和從右到左遍歷數組

#include <iostream>
#include <iterator>
#include <algorithm>
size_t gcd(size_t m, size_t n)
{
return n==0 ? m : gcd(n, m % n);
}
void rotate(int *arr, size_t n, int k) // n:數組長度， k:右移位數
{
size_t d = gcd(n, (k>0 ? k: -k)); // 獲得n和|k|的最大公約數
for (size_t i = 0; i < d; i++)
{
int tmp = arr[i];
size_t prev_pos = i;
size_t cur_pos = prev_pos;
while ((prev_pos = (prev_pos+n-k)%n) != i)
{
arr[cur_pos] = arr[prev_pos];
cur_pos = prev_pos;
}
arr[cur_pos] = tmp;
}
}
// 測試代碼
int main()
{
using std::;
using std::ostream_iterator;
using std::cout;
using std::endl;
const size_t SIZE = 18;
const int RIGHT = 12;
int arr[SIZE];
for (int i = 0; i < SIZE; i++)
arr[i] = i;
rotate(arr, SIZE, RIGHT);
(arr, arr+SIZE, ostream_iterator<int>(cout, " "));
system("pause");
}
對於可隨機訪問的數組,有比三次convert更快的演算法,如上所示(STL中對Random Access Iterator即使用此演算法).
LZ的演算法與此相同,只不過不需要check.數學上可以證明只要循環gcd(n,k)次就可遍歷所有元素恰好一次.
該演算法的時間復雜度為n+gcd(n,k),即每個數組元素恰好賦值一次,每個循環需有一次臨時變數的賦值.