图的遍历算法包括： 1. 深度优先搜索. 2. 广度优先搜索
1. 深度优先搜索 DFS （Depth First Search）
类似于二叉树的 先序遍历算法
算法： DFS(S)
- 访问
S顶点 - 若
S尚有未被访问的邻接点，则任取其一u，递归执行DFS(u)
否则，依次退回到最近被访问的顶点
注：典型的递归调用，为提高递归的效率，防止重复计算，通常引入一个标记数组来标记已经访问过的顶点
代码模版
DFS Code：
//伪码实现，类似于树的先序遍历
void DFS(Vertex v){
visited[v] = true;
for(v 的每个邻接点 W){
if(!visited[W]){
DFS(W);
}
}
}
/*******************************/
bool Visited[MAX_VERTEX_NUM]; // 标记数组
void DFS(Graph G, int v)
{
visit(v);
Visted[v] = true;
for (w = FirstNeighbour(G,v); w >= 0; w = NextNeighbour(G,v,w)) {
// 枚举 v 的每一个邻接点 w
if (!Visited[w]) { // w 为 v 的尚未访问的邻接点
DFS(G, w); // 以 w 为顶点，递归执行DFS
}
}
}
// 利用 DFS 遍历图G
void DFSTraverse(Graph G)
{
for (int v = 0; v < G.vexNum; ++ v) {
Visited[v] = false;
}
for (int v = 0; v < G.vexNum; ++ v) {
// 本模板从 v=0 开始遍历
if (!Visited[v]) {
DFS(G, v);
}
}
}
// 这个方法的作用在于，若图G为非连通图（多个连通域），仍可以深度遍历所有的顶点
DFS算法性能分析：
DFS是一个递归算法，需借助栈，空间复杂度为 O(|V|)
遍历图的实质是对每个顶点查找其邻接点的过程
以邻接矩阵存储的图为例 ：查找每个顶点的邻接点所需的时间为O(|V|)，故遍历全图的总时间为O(|V * V|)
（邻接表，O(|E|)，O(|V|＋|E|)）
补充：
深度优先遍历会产生一棵深度优先生成树，条件是： 对连通图调用DFS
否则产生的将是深度优先生成森林
-
图例 ：对非(强)连通有向图G进行 DFS 有
DFS
2. 广度优先搜索 BFS （Breadth First Search）
类似于二叉树的 层次遍历算法
算法 ：始于顶点S的广度优先搜索
- 访问顶点
S - 依次访问
S所有尚未访问的邻接顶点 - 依次访问它们
尚未访问的邻接顶点
... ... - 如此反复执行 3 ，直到没有
尚未访问的邻接顶点
广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像DFS那样，有回退过程。因此BFS不是一个递归算法，为了实现逐层访问，必须借助一个辅助队列
代码模版
BFS Code ：
bool Visited[MAX_VERTEX_NUM];
void BFS(Graph G, int v)
{ // 从顶点v开始，借助一个一个辅助队列 Q
visit(v); // 访问 v
Visited[v] = true; // 标记为已访问
Enqueue(Q, v); // 将顶点 v 入队列
while (!Q.empty()) { // 队列不空
Dequeue(Q, v); // 出队列 v顶点
for (w = FirstNeighbour(G,v); w >= 0; w = NextNeighbour(G,v,w)) { // 检测v所有的邻接点
if (!Visited[w]) { // w为v未fangwen的邻接点
visite(w);
Visited[w] = true;
Enqueue(Q, w); // 顶点w入队
}
}
}
}
// 一幅图G中可能含有多个连通域，从一个顶点s出发，未必能够到达其他连通域，so，如何处理？使BFS适用于整幅图，而不是特定的连通域
void BFSTraverse(Graph G)
{
for (int i = 0; i < G.vexNum; ++i) {
Visited[i] = false;
}
InitQueue(Q); // 初始化辅助队列Q
for (int i = 0; i < G.vexNum; ++i) {
if (!Visited[i]) {
BFS(G,i);
}
}
}
BFS算法性能分析：
最坏情况下，空间复杂度为O(|V|)
时间复杂度：
- 邻接矩阵，总的时间复杂度为
O(|V|*|V|)平方 - 邻接表，总的时间复杂度为
O(|V|+|E|)
BFS算法的应用
-
单源最短路径问题 ： 图G中，顶点
u到顶点v的最短路径
G = (V , E)为非带权图，定义从顶点u到顶点v的最短路径d(u,v)为u到v的所有路径中最短的路径长度（边数最少），若u到v没有通路，则d(u,v) = ∞，实现求顶点u到顶点v的最短路径
d(u,v)
利用BFS算法来求解
单源最短路径问题 Code
主框架实现是 BFS算法
- 广度优先生成树 ：
