图的遍历

算法 算法
创建时间:
字数:1.8k 阅读: 评论:
  1. DFS模板
  2. BFS模板
  3. DFS
    1. 模板
    2. DFS 解决N皇后问题实例
  4. N叉树的遍历框架
  5. 图像填充问题

DFS模板

1
2
3
4
5
dfs出口，不满足条件就退出

操作

递归，接着进一步DFS

BFS模板

1
2
3
4
5
6
7
8
9
10
11
条件判断（边界判断，其他要求的判断）

创建队列

在队列中加入第一个满足条件的元素

while(队列不为空) {
    取出队列头部元素
    操作
    根据头部元素，往队列中再次加入满足条件的元素
}

DFS

深度优先搜索适合解决必须走到最深处(例如对于树，须走到它的叶子节点)才能得到一个解的问题。通常利用递归实现，所以每次递归开始的时候要判断是否达到收敛条件，若达到了则得到一个可行解，若没达到，则对当前状态进行扩展（扩展的时候通常会根据实际情况过滤掉一些非法的状态，这个过程叫剪枝，适当的剪枝有时能极大地提高搜索的速度），如果要求输出具体解，则此时应该保存该状态，当扩展结束后，需要释放这个保存的状态。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* dfs 模板.
* @param[in] input 输入数据指针
* @param[inout] cur or gap 标记当前位置或距离目标的距离
* @param[out] path 当前路径，也是中间结果
* @param[out] result 存放最终结果
* @return 路径长度，如果是求路径本身，则不需要返回长度
*/
void dfs(type *input, type *path, int cur or gap, type *result) {
  if (数据非法) return 0; // 终止条件
  if (cur == input.size( or gap == 0)) { // 收敛条件
    将 path 放入 result
  }
  if (可以剪枝) return;
  for(...) { // 执行所有可能的扩展动作
     执行动作，修改 path
     dfs(input, step + 1 or gap--, result);
     恢复 path
  }
}

DFS 解决N皇后问题实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
	vector<vector<string> > solveNQueens(int n) {
		column=vector<int>(n,0);
		principle_diagonals=vector<int>(2*n,0);
		counter_diagonals=vector<int>(2*n,0);
		vector<int> C(n,0);  //C[i]的值表示第i行皇后所在的列
		vector<vector<string>> result;
		DFS(result,C,0);
		return result;
	}
private:
	vector<int> column;  //column[i]表示第i行皇后所在的列
	vector<int> principle_diagonals;  //表示主该主对角线是否已经有皇后
	vector<int> counter_diagonals;  //表示副对角线是否已经有皇后
	void DFS(vector<vector<string> >& result,vector<int>&C ,int row)
	{
		int n=C.size();
		if(row==n)    //收敛条件
		{
			string tmpStr(n,'.');
			vector<string>tmpResult(n,tmpStr);
			for(int i=0;i<n;++i)
			{
				tmpResult[i][C[i]]='Q';
			}
			result.push_back(tmpResult);
			return;
		}
		for(int i=0;i<n;++i)
		{
			bool ok=column[i]==0&&principle_diagonals[row+i]==0 && counter_diagonals[n-row+i]==0;
			if(ok)  //用于剪枝，只扩展合法的状态
			{
				//执行扩展
				column[i]=principle_diagonals[row+i]=counter_diagonals[n-row+i]=1;
				C[row]=i;
				DFS(result,C,row+1);
				//撤销扩展
				column[i]=principle_diagonals[row+i]=counter_diagonals[n-row+i]=0;
				C[row]=0;
			}
		}
	}
};
 
int _tmain(int argc, _TCHAR* argv[])
{
	vector<vector<string>> result;
	Solution sln;
	result=sln.solveNQueens(4);
	for (int i=0;i<result.size();++i)
	{
		for (int j=0;j<result[0].size();++j)
		{
			cout<<result[i][j]<<endl;
		}
		cout<<endl;
		cout<<endl;
	}
	return 0;
}

N叉树的遍历框架

void traverse(TreeNode root) {
for (TreeNode child : root.children)
traverse(child)
}

图像填充问题

又称四叉树的广度优先遍历

floodfill问题
一、构建框架
此题可以抽象成一个二维矩阵（图片其实就是像素点矩阵），然后从某个点开始向四周扩展，直到无法再扩展为止。

矩阵，可以抽象为一幅【图】，这就是一个图的遍历问题，也就类似一个 N 叉树遍历的问题。几行代码就能解决，直接上框架吧：

1
2
3
4
5
6
7
8

// (x, y) 为坐标位置
void fill(int x, int y) {
    fill(x - 1, y); // 上
    fill(x + 1, y); // 下
    fill(x, y - 1); // 左
    fill(x, y + 1); // 右
}

这个框架可以解决所有在二维矩阵中遍历的问题，说得高端一点，这就叫深度优先搜索（Depth First Search，简称 DFS），说得简单一点，这就叫四叉树遍历框架。坐标 (x, y) 就是 root，四个方向就是 root 的四个子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int[][] floodFill(int[][] image,
        int sr, int sc, int newColor) {

    int origColor = image[sr][sc];
    fill(image, sr, sc, origColor, newColor);
    return image;
}

void fill(int[][] image, int x, int y,
        int origColor, int newColor) {
    // 出界：超出边界索引
    if (!inArea(image, x, y)) return;
    // 碰壁：遇到其他颜色，超出 origColor 区域
    if (image[x][y] != origColor) return;
    image[x][y] = newColor;
    
    fill(image, x, y + 1, origColor, newColor);
    fill(image, x, y - 1, origColor, newColor);
    fill(image, x - 1, y, origColor, newColor);
    fill(image, x + 1, y, origColor, newColor);
}

boolean inArea(int[][] image, int x, int y) {
    return x >= 0 && x < image.length
        && y >= 0 && y < image[0].length;
}

只要你能够理解这段代码，一定要给你鼓掌，给你 99 分，因为你对【框架思维】的掌控已经炉火纯青，此算法已经 cover 了 99% 的情况，仅有一个细节问题没有解决，就是当 origColor 和 newColor 相同时，会陷入无限递归。

二、研究细节
为什么会陷入无限递归呢，很好理解，因为每个坐标都要搜索上下左右，那么对于一个坐标，一定会被上下左右的坐标搜索。被重复搜索时，必须保证递归函数能够能正确地退出，否则就会陷入死循环。

三、处理细节
如何避免上述问题的发生，最容易想到的就是用一个和 image 一样大小的二维 bool 数组记录走过的地方，一旦发现重复立即 return。

1
2
3
4
5
6
7
8
9

 // 出界：超出边界索引
if (!inArea(image, x, y)) return;
// 碰壁：遇到其他颜色，超出 origColor 区域
if (image[x][y] != origColor) return;
// 不走回头路
if (visited[x][y]) return;
visited[x][y] = true;
image[x][y] = newColor;

这种边界的处理方法是最值得探讨和学习的尤其是重复访问时应该怎么办？

一般想到的都是设置一个标志用来标记这个位置是否已经被访问过了

完全 OK，这也是处理「图」的一种常用手段。不过对于此题，不用开数组，我们有一种更好的方法，那就是回溯算法。

前文【回溯算法详解】讲过，这里不再赘述，直接套回溯算法框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void fill(int[][] image, int x, int y,
        int origColor, int newColor) {
    // 出界：超出数组边界
    if (!inArea(image, x, y)) return;
    // 碰壁：遇到其他颜色，超出 origColor 区域
    if (image[x][y] != origColor) return;
    // 已探索过的 origColor 区域
    if (image[x][y] == -1) return;
    
    // choose：打标记，以免重复
    image[x][y] = -1;
    fill(image, x, y + 1, origColor, newColor);
    fill(image, x, y - 1, origColor, newColor);
    fill(image, x - 1, y, origColor, newColor);
    fill(image, x + 1, y, origColor, newColor);
    // unchoose：将标记替换为 newColor
    image[x][y] = newColor;
}

这种解决方法是最常用的，相当于使用一个特殊值 -1 代替 visited 数组的作用，达到不走回头路的效果。为什么是 -1，因为题目中说了颜色取值在 0 - 65535 之间，所以 -1 足够特殊，能和颜色区分开。

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 583614868@qq.com

赏

文章标题:图的遍历

文章字数:1.8k

本文作者:钟帅豪

发布时间:2019-11-11, 09:12:29

最后更新:2020-11-23, 15:37:57

原始链接:http://jhshz520.github.io/2019/11/11/图的遍历/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

©2019-2022 钟帅豪

Built with Hexo and 3-hexo theme

目录
×

喜欢就点赞,疼爱就打赏