图论之搜索

2014/11/07

Categories: Algorithm Tags: acm graph theory

搜索在图论中有着广泛的应用。许多图的问题需要遍历整个图,才能获得最优解。
深度优先搜索和广度优先搜索是图论中最常用的两种搜索技巧。

深度优先搜索,简称为”dfs”,所遵循的搜索策略是尽可能“深”地搜索。它的基本思想是:为了求得问题的解,先选择某一种可能情况向前(子结点)探索,在探索过程中,一旦发现原来的选择不符合要求,就回溯至父亲结点重新选择另一结点,继续向前探索,如此反复进行,直至求得最优解。深度优先搜索的实现方式可以采用递归或者栈来实现。深搜在求解图的连通性等问题上有着广泛的应用。

对图 G 进行深度优先搜索,会产生一个深度优先搜索树,在搜索时对顶点加上搜索的时间戳,这个搜索树会显现一些良好的性质,我们用 dfn 数组记录深度优先访问的某顶点的时间, visited 数组记录某顶点是否已经被访问过。

  1. 从图 G 某一顶点 v 开始深度优先搜索过程:标记 v 已经被访问过,深度优先搜索 v 的邻接顶点 u
  2. 然后递归地进行这一过程,直到此刻访问的顶点 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 图 2.1 深搜图

深搜,某种意义上,可以称之为一种枚举,在不剪枝的情况下,会尽可能的搜索所有可能状态,直到找到解为止,时间复杂度通常呈几何速度增长。当深搜应用于图的遍历时,若图采用邻接表的储存形式,它的时间复杂度将是 O(|E|)

剪枝

剪枝不是某种特定算法。它是对于,在搜索算法上,排除某些搜索情况,减少大量无效分支的代码技巧的统称。就像一棵树,剪去不必要的枝条,以降低时间规模。

常见的剪枝技巧包括奇偶剪枝法。

广度优先搜索,简称“bfs”,顾名思义,尽可能广地进行搜索。它的思想是从一个顶点开始,辐射状地优先遍历其周围较广的区域。

广度优先搜索使用队列来实现。

  1. 初始化: 从图 G 某一顶点 src 开始,将其存入一个队列 visit_queue, 并标记 v 已经被访问过。
  2. 从队列弹出队首 v,依次访问顶点的邻接顶点 u,如果顶点 u 没有被访问过,则将 u 存入队列,并标记 u 已经被访问过,否则跳过该顶点 u
  3. 重复过程 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 图 2.2 广搜图