搜索在图论中有着广泛的应用。许多图的问题需要遍历整个图，才能获得最优解。
深度优先搜索和广度优先搜索是图论中最常用的两种搜索技巧。
深度优先搜索(Depth-First-Search)
深度优先搜索，简称为"dfs"，所遵循的搜索策略是尽可能“深”地搜索。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前（子结点）探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点重新选择另一结点，继续向前探索，如此反复进行，直至求得最优解。深度优先搜索的实现方式可以采用递归或者栈来实现。深搜在求解图的连通性等问题上有着广泛的应用。
对图 G 进行深度优先搜索，会产生一个深度优先搜索树，在搜索时对顶点加上搜索的时间戳，这个搜索树会显现一些良好的性质，我们用 dfn 数组记录深度优先访问的某顶点的时间， visited 数组记录某顶点是否已经被访问过。
- 从图
G某一顶点v开始深度优先搜索过程：标记v已经被访问过，深度优先搜索v的邻接顶点u； - 然后递归地进行这一过程，直到此刻访问的顶点
v没有邻接顶点或者它的邻接顶点已经全被标记过时，进行回溯。
代码
void dfs(int v) {
visited[v] = true;
dfn[v] = time++;
// 依次访问顶点 v 的邻接顶点
for(int i = head[v]; i != -1; i = edge[i].pre) {
int u = edge[i].cur;
if(visited[u] == fasle) {
printf("%d ", u);
visited[u] = true;
dfs(u);
}
}
}
图 2.1 深搜图
深搜，某种意义上，可以称之为一种枚举，在不剪枝的情况下，会尽可能的搜索所有可能状态，直到找到解为止，时间复杂度通常呈几何速度增长。当深搜应用于图的遍历时，若图采用邻接表的储存形式，它的时间复杂度将是 O(|E|)。
剪枝
剪枝不是某种特定算法。它是对于，在搜索算法上，排除某些搜索情况，减少大量无效分支的代码技巧的统称。就像一棵树，剪去不必要的枝条，以降低时间规模。
常见的剪枝技巧包括奇偶剪枝法。
广度优先搜索（Breadth-First-Search）
广度优先搜索，简称“bfs”，顾名思义，尽可能广地进行搜索。它的思想是从一个顶点开始，辐射状地优先遍历其周围较广的区域。
广度优先搜索使用队列来实现。
- 初始化： 从图
G某一顶点src开始，将其存入一个队列visit_queue, 并标记v已经被访问过。 - 从队列弹出队首
v，依次访问顶点的邻接顶点u，如果顶点u没有被访问过，则将u存入队列，并标记u已经被访问过，否则跳过该顶点u； - 重复过程 1 直到队列为空，此时所有顶点都被访问过，搜索结束。
广度优先搜索通常用于迷宫问题，找出某点到某点的最短距离。由于广搜是分层的，离源点 src 越近其所在层次（depth）越低，其最短距离即是其所在层次数。
代码
void bfs(int src) {
queue<int> visit_queue;
visit_queue.push(src);
visited[src] = true;
depth[src] = 0;
while(visit_queue.empty() == false) {
int v = visit_queue.front();
visit_queue.pop();
// 依次访问 v 的子节点
for(int i = head[v]; i != -1; i = edge[i].pre) {
int u = edge[i].cur;
if(visited[u]) continue;
depth[u] = depth[v] + 1;
visit_queue.push(u);
visited[u] = true;
printf("%d ", u);
}
}
}
图 2.2 广搜图