在网格中确定连续着色区域的算法是什么？

Question

给定一个基本网格（就像一张图表纸），其中每个单元格都随机地填充了n种颜色之一，是否存在一种可靠的算法，可以告诉我有哪些连续区域（相同颜色的单元格组成的相邻单元格集合）？假设n是一个合理的数字，比如5。

我有一些想法，但它们都感觉效率极低。

- Mr Snug

Answer 1

最佳算法的时间复杂度为O(单元格数量)，与颜色数量无关。

可以通过遍历每个单元格来实现，每次访问一个未标记为已访问的单元格，进行一次图遍历以找到该区域中所有连续的单元格，然后继续遍历。

编辑：

这里是深度优先搜索的简单伪代码示例，它是一种易于实现的图遍历算法：

function visit(cell) {
    if cell.marked return
    cell.marked = true
    foreach neighbor in cell.neighbors {
        if cell.color == neighbor.color {
            visit(neighbor)
        }
    }
}

- recursive

---

你能具体说明一下“进行图遍历”吗？这是否需要使用递归算法？ - Mr Snug

图遍历将是一种洪水填充算法，正如其他答案中所涵盖的那样。 - Sparr

哦，深度优先搜索是一个非常糟糕的想法；很容易耗尽堆栈空间。请改为广度优先搜索（或维护自己的堆栈）。 - ShreevatsaR

按照定义，图遍历在迭代单元格之上，这不是O(n)。 - Tatarize

@Tatarize 不，即使在朴素实现中，只要图遍历和单元迭代操作于同一数据结构上，它也是O(n)的。图遍历是O(e)，但对于平面图而言，这是O(n)的。 - collapsar

Answer 2

除了递归的递归答案外，如果递归太慢，您可以使用堆栈：

function visit(cell) {
    stack = new stack
    stack.push cell

    while not stack.empty {
        cell = stack.pop
        if cell.marked continue
        cell.marked = true
        foreach neighbor in cell.neighbors {
            if cell.color == neighbor.color {
                stack.push neighbor
            }
        }
    }
}

- martinus

---

我认为这个想法是对矩阵（图）中的每个单元格调用visit(cell)，然后决定每种颜色的最大连接区域是哪一个。 - Rami Alshareef

Answer 3

您可以尝试对每个方格进行洪水填充。随着洪水的扩散，将网格方格记录在数组或其他东西中，并用未使用的颜色（例如-1）着色。

- Rocketmagnet

Answer 4

这里有一篇与泛洪填充相关的维基百科文章，可能对你有帮助：http://en.wikipedia.org/wiki/Flood_fill

- Dan Ellis

Answer 5

并查集 也可以在这里使用。事实上，你可以把问题转化为一个关于图的问题：顶点是格子单元，如果它们的格子颜色相同，则两个顶点相邻。你的目标是找到连通块。

使用并查集数据结构的方法如下：首先创建一个并查集数据结构，其元素数量与单元格数相同。然后迭代遍历每个单元格，并且如果它们具有相同的颜色，则将其 union 起来。最后，在每个单元格上运行 find 并存储响应结果。具有相同 find 的单元格属于同一连续的彩色区域。

- A. Rex

Answer 6

您可以通过扫描线迭代区域，从左到右，从上到下。对于每个单元格，您需要创建一个共享相同内存对象的单元格列表。对于每个单元格，您需要将当前单元格添加到该列表中（与其共享或新建）。然后，如果右侧或下方的单元格颜色相同，则将该列表与该单元格共享。如果该单元格已经有一个列表，则合并列表并用新合并的列表替换列表中列出的每个单元格中的列表对象引用。

然后，每个单元格中都有一个指向包含该单元格的每个连续单元格的列表的引用。这很好地结合了每个单元格之间的泛洪工作。而不是为每个单元格重复此操作。由于您有列表，因此用合并数据替换数据只需遍历列表即可。它的时间复杂度为O(n*c)，其中n是单元格数，c是图形连续性的度量。完全不连续的网格将是n次。完全连续的1色图将是n^2/2。

- Tatarize

Answer 7

如果你想要更精细的控制，可以考虑使用A*算法，并利用启发式方法来包含颜色相似的瓦片。

- Hazar

Answer 8

我在一个视频中听到了这个问题，也在这里找到了它，并想出了我在搜索中看到的最佳方法。以下是算法的基本步骤：

循环遍历数组（假设颜色网格被表示为二维数组），从左上到右下。 当遍历第一行时，只需检查左边的颜色是否相同。当遍历所有后续行时，检查上方和左边的单元格 - 这比每次检查顶部、底部、左侧和右侧更有效。不要忘记检查左侧单元格是否越界。 创建类型为<int,Dictionary<int,Hashset<cell>>>的字典，用于存储颜色和这些颜色内的组。哈希集合包含单元格位置（具有2个属性的单元格对象：整数行，整数列）。 如果单元格在顶部或左侧未连接到相同颜色的单元格，则创建新的字典条目、该条目内的新颜色组，并将当前单元格添加到该组（哈希集合）中。否则，它与同一颜色的另一个单元格相连；将当前单元格添加到包含它所连接单元格的颜色组中。 如果您在某个时候遇到顶部和左侧具有相同颜色的单元格，则如果它们都属于同一颜色组，那么很容易，只需将当前单元格添加到该颜色组中。否则，检查左上角单元格。如果它与当前单元格的颜色不同，并且顶部和左侧单元格属于不同的颜色组，则将两个颜色组合并在一起；将当前单元格添加到该组中。 最后，循环遍历所有哈希集合，看看哪个计数最高 - 这将是返回值。

这是一个我制作的视频链接，包含了视觉和全面的解释： https://d.tube/#!/v/israelgeeksout77/wm2ax1vpu3y

P.S. 我在GeeksForGeeks上找到了这篇文章 https://www.geeksforgeeks.org/largest-connected-component-on-a-grid/

他们很贴心地发布了这个问题的源代码，使用多种编程语言实现！但是我尝试了他们的代码和我的代码，我的代码运行时间大约是他们的1/3。

- SendETHToThisAddress