不看就不记得的广度深度优先遍历！
深度优先遍历
（类似于树的先序遍历）
1
2
3
4
5
6
7
8
9
10
11
12
|
伪代码：
void DFS(vertex V)
{
visited[v] = true;
for (v 的每一个邻接点 w )
if(visted[w] == false) //没有被访问过
DFS(w)
}
|
广度优先遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
伪代码：
void BFS(vertex V)
{
visited[v] = true;
enqueue(v,Q) //将该点加入队列
while(Q is not empty) //只要队列不空
{
v = dequeue(Q) //从队列中取出一个
for(v 的每一个邻接点 w)
if(visited[w] == false) //没有被访问
enqueue(w,Q) //将该点加入队列
visited[w] = true; //设置访问标志
}
}
|
无权图的单源最短路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void Unweighted ( Vertex S )
{
Enqueue(S, Q);
while(!IsEmpty(Q))
{
V = Dequeue(Q);
for ( V 的每个邻接点 W )
if ( dist[W] == -1 )
{
dist[W] = dist[V]+1; //s到w 的最短路径
path[W] = V; //s到w 的最短路径所经过的点 v
Enqueue(W, Q);
}
}
}
|
有权图的单源最短路径
Dijkstra算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| Dijkstra(Vertex v)
{
while(1)
{
v = 未收录顶点中dist最小的；
if(不存在这样的v,也就是所有的点都收录了)
break;
collected[V] = true;
for(v 每一个邻接点 w)
{
if(collected[w] == false)
{
if(dist[v]+e<v,w> < dist[w]) //小则更新
dist[w] = dist[v] + e<v,w>
path[w] = V
}
}
}
}
|
冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void bubble_sort(A[],n)
{
for(int i=n-1;i>=0;i--)
{
int flag = 0;
for(int j=0;j<i;j++) //一趟冒泡排序
{
if(A[i] > A[i+1])
{
swap(A[i],A[i+1])
flag = 1 //标志发生了交换
}
}
if(flag == 0 )
break //全程都没有交换，证明序列已经有序
}
}
|
插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| void insert_sort(A[],n)
{
for(int i=1;i<n;i++)
{
tmp = A[i]
for(int j=i;j>0;j--)
{
if(A[i] < A[j])
{
A[i] = A[i-1]
}
else
break
}
A[i] = tmp
}
}
|