遍历网格图（但图极大），有没有什么远超深度遍历、广度遍历的针对性更优算法？

getstr88 · 发表于 2022-6-14 21:14

本帖最后由 getstr88 于 2022-6-14 21:27 编辑

如下图所示这样的方格子（数量巨大，几十万×几十万个），要求随便指定一个格子坐标（x，y），得到所有与其上下左右连通（不能斜着）且数字相同的格子的坐标

深度优先遍历是完全不可行：因为这么多格子，会递归调用极大层数，而我实测，C#程序，一个函数自己递归调用自己差不多到2600多层时，直接报堆栈溢出
广度遍历不会出现上面问题，但是内存耗费巨大，越往外层符合的越多，需要存储的数据越大，导致程序占用内存极大，超出原定允许的性能指标
如果强制要分而治之，说实在的，这代码很难写，因为你要判断每个小块旁边的小块是不是也要涉及到，而且是从哪个像素开始连接的，想想也是自己给自己找麻烦

所以问下，针对这种方格的遍历，有什么好算法么？

剑眉书生 · 发表于 2022-6-14 21:22

你说的是什么

getstr88 · 发表于 2022-6-14 21:28

剑眉书生发表于 2022-6-14 21:22
你说的是什么

如下图所示这样的方格子（数量巨大，几十万×几十万个），要求随便指定一个格子坐标（x，y），得到所有与其上下左右连通（不能斜着）且数字相同的格子的坐标

howyouxiu · 发表于 2022-6-14 21:49

这哪里需要遍历，直接：
1.对于二维数组中指定的坐标
2.分别计算出上下左右的坐标
3.取出坐标对应的值去判断

unmask · 发表于 2022-6-14 22:10

图论，欧拉路径算法，前提是找到合适的图数据结构表达你的方格子，哪些是顶点vetex，哪些是边edge等

hrdom · 发表于 2022-6-14 22:13

https://www.zhihu.com/question/55844897
找出无向图的所有连通子图

hrdom · 发表于 2022-6-14 22:14

hrdom 发表于 2022-6-14 22:13
https://www.zhihu.com/question/55844897
找出无向图的所有连通子图

抽象出来的问题大概就是这个，至于算法嘛，好像就那3种

hrdom · 发表于 2022-6-14 22:26

至于dfs爆栈嘛，要不搜搜如何扩大栈大小，反正dfs还是比较好写的

~零度 · 发表于 2022-6-14 22:43

初始像素点p0的值为x0
集合S1：上下左右四个邻居像素点未全部检查的像素点
集合S2：已完成对四个邻居像素检查的像素点
将p0加入集合S1

从S1中任取一个像素点p，检查其上下左右4个邻居像素，若值为x0且不在S1和S2中，则将该邻居像素加入S1，检查完成后将像素点p从S1中去除，并加入S2

重复以上过程直到集合S1为空，最后输出S2中像素点的坐标

最极端的情况下（全图像素点的值相同），每一个像素点都需要访问四次

getstr88 · 发表于 2022-6-14 22:45

~零度发表于 2022-6-14 22:43
初始像素点p0的值为x0
集合S1：上下左右四个邻居像素点未全部检查的像素点
集合S2：已完成对四个邻居像素 ...

这不就是广度遍历，一点都不差。我上面已经说过了，不符合内存的要求

帐号		自动登录	找回密码
密码			注册[Register]

[求助] 遍历网格图（但图极大），有没有什么 远超 深度遍历、广度遍历的针对性更优算法？

[求助] 遍历网格图（但图极大），有没有什么远超深度遍历、广度遍历的针对性更优算法？