遍历所有元素的算法

㈠ 求高手给个遍历算法

图的遍历

从图中某一顶点出发访遍图中其余顶点，且使每一顶点仅被访问一次。这一过程叫做图的遍历。
遍历图的基本方法有两种：深度优先搜索和广度优先搜索。这两种方法都适用于有向图和无向图。
和树的遍历类似，图的遍历也是从某个顶点出发，沿着，某条边搜索路径对图中所有顶点各作一次访问。若给定的图是连通图，则从图中任意顶点出发顺着边可以访问到该图中所有的顶点，然而，图的遍历比树的遍历复杂得多，这是因为图中的任一点都可能和其余顶点相邻接，故在访问了某个顶点之后，可能顺着某条回路又到了该顶点。为了避免重复访问同一个顶点，必须记住每个顶点是否被访问过。为此，可设置一个布尔向量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),即每个数组元素恰好赋值一次,每个循环需有一次临时变量的赋值.