algorithm

本文介绍深度遍历算法和广度遍历算法。以一个迷宫为例。

// 迷宫, 1 代表障碍,0 代表通路
// 起点是 (1,1),终点是 (8,8)
int[][] maze = {            
    {1,1,1,1,1,1,1,1,1,1},
    {1,0,0,1,0,0,0,1,0,1},
    {1,0,0,1,0,0,0,1,0,1},
    {1,0,0,0,0,1,1,0,0,1},
    {1,0,1,1,1,0,0,0,0,1},
    {1,0,0,0,1,0,0,0,0,1},
    {1,0,1,0,0,0,1,0,0,1},
    {1,0,1,1,1,0,1,1,0,1},
    {1,1,0,0,0,0,0,0,0,1},
    {1,1,1,1,1,1,1,1,1,1}
};

1. 深度优先遍历

深度优先遍先(Depth First Search)利用了回溯思想,属于图算法的一种。

思想:如果前面有路,就往前走,如果没有,返回到上一个分叉口,走另一条路,直到达到目的地。侧重点在纵深。

bool DFS(int i, int j){
	maze[i][j] = 1;   // 访问过的置一,表示不再访问 
	if(i == END && j == END) return true;
	if(!maze[i][j-1] && DFS(i, j-1)) {  // up 
		std::cout << "(" << i << "," << j-1 << ")" << std::endl;
		return true;
	} 
	if(!maze[i][j+1] && DFS(i, j+1)) { // down 
		std::cout << "(" << i << "," << j+1 << ")" << std::endl;
		return true;
	}
	if(!maze[i+1][j] && DFS(i+1, j)) { // right 
		std::cout << "(" << i+1 << "," << j << ")" << std::endl;
		return true;
	}
	if(!maze[i-1][j] && DFS(i-1, j)) { // left 
		std::cout << "(" << i-1 << "," << j << ")" << std::endl;
		return true;
	} 
	return false;
}

用途:网络爬虫、最大路径问题

2. 宽度优先遍历

相比于深度优先遍历,宽度优先遍历(Breadth First Search)更注重周边环境,所以会向周围任何路径进行搜索,直到搜索到第一个结果为止。因此经常用在寻找最短路径之类的问题中。